Фермер Джон понимает, что дохода, который он получает от производства молока, недостаточен для финансирования роста его фермы, поэтому, чтобы заработать дополнительные деньги, он запускает услугу аренды коров, которую он называет "USACOW" (произносится "Use-a-cow").

У фермера Джона есть n коров, каждая из которых может давать какое-то количество молока каждый день. Каждый из m магазинов возле фермы ФД предлагает купить определенное количество молока по определенной цене. Более того, r соседних фермеров фермера Джона заинтересованы в аренде коровы по определенной цене.

Фермер Джон должен выбрать, следует ли доить каждую корову или сдавать ее в аренду соседнему фермеру. Помогите ему найти максимальную сумму денег, которую он может заработать в день.

Входные данные

Первая строка содержит числа n (1 ≤ n ≤ 105), m (1 ≤ m ≤ 105) и r (1 ≤ r ≤ 105). Каждая из следующих n строк содержит целое число ci (1 ≤ ci ≤ 106), указывающее, что i - ая корова ФД может производить ci галлонов молока каждый день. В следующих m строках записано по два целых числа qi и pi (1 ≤ qi, pi ≤ 106), указывая на то, что i - ый магазин готов покупать до qi галлонов молока по pi за галлон. Имейте в виду, что ФД может продать любое количество молока от нуля до qi галлонов в данный магазин. Каждая из следующих r строк содержит целое число ri (1 ≤ ri ≤ 106), указывающее, что один из соседей фермера Джона хочет арендовать корову за ri центов в день.

Выходные данные

Выведите максимальную прибыль, которую фермер Джон может получить за день от доения или сдачи в аренду каждой из своих коров. Обратите внимание, что вывод может быть слишком большим для стандартного 32-битного целого числа, поэтому Вам может потребоваться использовать более крупный целочисленный тип, например long long в C/C++.

Пример

Фермер Джон должен доить коров #1 и #4, чтобы произвести 13 галлонов молока. Он должен полностью выполнить заказ на 10 галлонов, заработав 250 центов, и продать оставшиеся три галлона по 15 центов каждый, получив в общей сложности 295 центов прибыли от молока.

Затем он должен сдать в аренду остальных трех коров за 250, 80 и 100 центов, чтобы заработать 430 центов (он должен оставить заявку на 40 центов аренды незаполненной). Всего получится 725 центов ежедневной прибыли.