Giải bài trực tuyến

Khu vực đặt các bể xăng của một Tổng Công Ty Xăng Dầu có dạng một hình chữ nhật được chia thành m * n ô vuông. Các ô vuông được đánh tọa độ 1 -> m từ trên xuống, 1 -> n từ trái sang.
Tại k ô của lưới có đặt các bể xăng. Người ta cần xây dựng một hệ thống đèn pha chiếu sáng, mỗi đèn chỉ chiếu dọc theo hoặc là hàng hoặc là cột của lưới ô vuông sao cho mỗi bể chứa xăng phải được chiếu sáng bởi ít nhất một đèn pha chiếu dọc theo hàng hoặc cột chứa nó. Biết:
- ai là chi phí xây dựng đèn chiếu sáng dọc theo hàng.
- bj là chi phí xây dựng đèn chiếu sáng dọc theo cột.

Yêu cầu: Tìm cách xây dựng hệ thống đèn với tổng chi phí xây dựng là nhỏ nhất.

Input

- Dòng đầu tiên chứa 3 số nguyên dương m, n, k (m, n <= 100).
- Dòng thứ hai chứa m số nguyên a1, a2, ..., am.
- Dòng thứ ba chứa n số nguyên b1, b2, ..., bn.
- Dòng thứ i trong k dòng tiếp theo chứa tọa độ của bể xăng thứ i.

Output

Một dòng duy nhất ghi tổng chi phí theo cách xây dựng tìm được.

Example

Input:
2 3 4
15 17
2 4 6
1 1
2 2
2 3
2 1

Output:
12