Bác nông dân John nhận ra thu nhập từ việc sản xuất sữa không đủ để tài trợ cho sự phát triển của trang trại. Vì vậy, để kiếm thêm tiền, ông mở một dịch vụ cho thuê bò mang tên “USACOW” (đọc là “Use-a-cow”).

Bác nông dân John có \(N\) cô bò (\(1 \leq N \leq 100{,}000\)), mỗi cô có thể sản xuất một lượng sữa nhất định mỗi ngày. Mỗi cửa hàng trong số \(M\) cửa hàng gần trang trại của ông (\(1 \leq M \leq 100{,}000\)) đề nghị mua một lượng sữa nhất định với một mức giá nhất định. Ngoài ra, mỗi người trong số \(R\) nông dân hàng xóm của bác nông dân John (\(1 \leq R \leq 100{,}000\)) muốn thuê một cô bò với một mức giá nhất định.

Bác nông dân John phải chọn vắt sữa hay cho thuê đối với từng cô bò. Hãy giúp ông tìm số tiền lớn nhất có thể kiếm được mỗi ngày.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(M\) và \(R\). Mỗi dòng trong \(N\) dòng tiếp theo chứa một số nguyên \(c_i\) (\(1 \leq c_i \leq 1{,}000{,}000\)), cho biết cô bò thứ \(i\) của bác nông dân John có thể sản xuất \(c_i\) gallon sữa mỗi ngày. Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(q_i\) và \(p_i\) (\(1 \leq q_i, p_i \leq 1{,}000{,}000\)), cho biết cửa hàng thứ \(i\) sẵn sàng mua tối đa \(q_i\) gallon sữa với giá \(p_i\) xu mỗi gallon. Lưu ý rằng bác nông dân John có thể bán cho một cửa hàng bất kỳ lượng sữa nào từ \(0\) đến \(q_i\) gallon. Mỗi dòng trong \(R\) dòng tiếp theo chứa một số nguyên \(r_i\) (\(1 \leq r_i \leq 1{,}000{,}000\)), cho biết một người hàng xóm của bác nông dân John muốn thuê một cô bò với giá \(r_i\) xu mỗi ngày.

Dữ liệu ra

Kết quả gồm một dòng chứa lợi nhuận lớn nhất bác nông dân John có thể kiếm được mỗi ngày bằng cách vắt sữa hoặc cho thuê từng cô bò. Lưu ý rằng kết quả có thể quá lớn để lưu trong một số nguyên \(32\) bit tiêu chuẩn, vì vậy bạn có thể cần dùng kiểu số nguyên lớn hơn như long long trong C/C++.

Ví dụ

5 3 4
6
2
4
7
1
10 25
2 10
15 15
250
80
100
40

725

Nguồn

USACO 2018 January Contest, Silver — Rental Service

Tác giả bài toán: Jay Leeds.