Farmer John sở hữu một trang trại dài dọc theo đường cao tốc, có thể xem như một trục số một chiều. Trên trang trại có \(K\) bãi cỏ (\(1 \leq K \leq 2\cdot 10^5\)); bãi cỏ thứ \(i\) nằm tại vị trí \(p_i\) và có độ ngon \(t_i\) (\(0\le t_i\le 10^9\)). Đối thủ của Farmer John, Farmer Nhoj, đã bố trí \(M\) con bò của mình (\(1 \leq M \leq 2\cdot 10^5\)) tại các vị trí \(f_1 \ldots f_M\). Tất cả \(K+M\) vị trí này là các số nguyên phân biệt trong đoạn \([0,10^9]\).

Farmer John cần chọn \(N\) vị trí (\(1\le N\le 2\cdot 10^5\)), không nhất thiết là số nguyên, để đặt các con bò của mình. Các vị trí này phải khác những vị trí đã bị bò của Farmer Nhoj chiếm, nhưng Farmer John có thể đặt bò tại cùng vị trí với các bãi cỏ.

Người nông dân sở hữu con bò gần một bãi cỏ nhất sẽ được quyền sở hữu bãi cỏ đó. Nếu hai con bò của hai người nông dân cách bãi cỏ một khoảng bằng nhau thì Farmer Nhoj giành được bãi cỏ.

Cho biết vị trí các con bò của Farmer Nhoj cùng vị trí và độ ngon của các bãi cỏ, hãy xác định tổng độ ngon lớn nhất mà các con bò của Farmer John có thể giành được khi được bố trí tối ưu.

Dữ liệu vào

Dòng đầu tiên chứa \(K\), \(M\) và \(N\).

\(K\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(p_i\) và \(t_i\), cách nhau bởi dấu cách.

\(M\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(f_i\).

Dữ liệu ra

In ra một số nguyên biểu thị tổng độ ngon lớn nhất. Lưu ý rằng đáp án có thể quá lớn để lưu trong số nguyên 32 bit, vì vậy bạn có thể cần sử dụng số nguyên 64 bit (chẳng hạn long long trong C hoặc C++).

Phân nhóm

Tất cả các dữ liệu kiểm thử tuân theo các ràng buộc đã nêu.

Ví dụ

6 5 2
0 4
4 6
8 10
10 8
12 12
13 14
2
3
5
7
11

36

Nguồn

USACO 2021 December Contest, Silver — Closest Cow Wins. Tác giả: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=1158