Чтобы увеличить свой доход, Фермер Джон организовал сервис по аренде коров.
У ФД есть \(N\) коров (\(1 \leq N \leq 100,000\)), каждая способна производить
некоторое количество молока каждый день. \(M\) магазинов (\(1 \leq M \leq 100,000\))
недалеко от фермы Джона покупают определённое количество молока, каждый по своей
цене. Более того, \(R\) (\(1 \leq R \leq 100,000\)) соседних фермеров заинтересованы
в аренде коров по некоторой цене.
ФД должен выбрать для каждой коровы, доить её самому или отдать в аренду
соседнему фермеру. Помогите ФД определить максимальное количество денег,
которое он может заработать за один день.
ФОРМАТ ВВОДА (файл rental.in):
Первая строка ввода содержит \(N\), \(M\), \(R\). Каждая из следующих \(N\) строк
содержит целое число \(c_i\) (\(1 \leq c_i \leq 1,000,000\)), указывающее, что
\(i\)-ая корова ФД может произвести \(c_i\) галлонов молока в день. Каждая
из \(M\) строк содержит два целых числа \(q_i\) и \(p_i\) (\(1 \leq q_i, p_i \leq 1,000,000\)),
которые обозначают, что \(i\)-ый магазин готов купить \(q_i\) галлонов молока
по \(p_i\) центов за галлон. Имейте ввиду, что ФД может продавать любое количество
молока от 0 до \(q_i\) галлонов в этот магазин. Каждая из следующих \(R\) строк
содержит целое число \(r_i\) (\(1 \leq r_i \leq 1,000,000\)), означающее, что один
из соседей ФД хочет арендовать корову за \(r_i\) центов в день.
ФОРМАТ ВЫВОДА (файл rental.out):
Вывод должен содержать одну строку - максимальную прибыль ФД, которую он может
получить за один день, доя или сдавая в аренду каждую из своих коров.
Заметим, что ответ может оказаться большим, чтобы поместиться в 32-битное целое,
поэтому Вы должны использовать тип как "long long" в C/C++.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3 4
6
2
4
7
1
10 25
2 10
15 15
250
80
100
40
|
725
|