Орендні послуги
Фермер Джон зрозумів, що доходу від виробництва молока недостатньо для розширення його ферми, тому вирішив запустити послугу оренди корів під назвою "USACOW" (вимовляється "Юз-а-кау").
У фермера Джона є n корів, кожна з яких може давати певну кількість молока щодня. Кожен з m магазинів поблизу ферми Джона готовий купити певну кількість молока за певною ціною. Крім того, r сусідніх фермерів зацікавлені в оренді корів за певною ціною.
Фермер Джон повинен вирішити, чи доїти кожну корову, чи здавати її в оренду сусідньому фермеру. Допоможіть йому визначити максимальну суму грошей, яку він може заробити за день.
Вхідні дані
Перший рядок містить числа n (1 ≤ n ≤ 10^5), m (1 ≤ m ≤ 10^5) і r (1 ≤ r ≤ 10^5). Кожен з наступних n рядків містить ціле число c[i] (1 ≤ c[i] ≤ 10^6), що вказує, скільки галонів молока може виробляти i-та корова щодня. У наступних m рядках записано по два цілі числа q[i] і p[i] (1 ≤ q[i], p[i] ≤ 10^6), що означає, що i-ий магазин готовий купити до q[i] галонів молока по p[i] за галон. Зверніть увагу, що Джон може продати будь-яку кількість молока від нуля до q[i] галонів у даний магазин. Кожен з наступних r рядків містить ціле число r[i] (1 ≤ r[i] ≤ 10^6), що вказує, скільки центів на день готовий заплатити один із сусідів за оренду корови.
Вихідні дані
Виведіть максимальний прибуток, який фермер Джон може отримати за день від доїння або здачі в оренду кожної зі своїх корів. Зверніть увагу, що вивід може бути занадто великим для стандартного 32-бітного цілого числа, тому вам може знадобитися використовувати більший цілочисельний тип, наприклад long long у C/C++.
Приклад
Фермер Джон повинен доїти корів #1 і #4, щоб отримати 13 галонів молока. Він повинен повністю виконати замовлення на 10 галонів, заробивши 250 центів, і продати залишок три галони по 15 центів кожен, отримавши загалом 295 центів прибутку від молока.
Потім він повинен здати в оренду решту трьох корів за 250, 80 і 100 центів, щоб заробити 430 центів (він повинен залишити заявку на 40 центів оренди незаповненою). Всього вийде 725 центів щоденного прибутку.