Орендні послуги#10421

Орендні послуги

1 секунда

128 мегабайтів

Середня

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

У Фермера Джона є $n$ корів, кожна з яких здатна давати деяку кількість молока щодня. Кожен з $m$ магазинів поблизу ферми Фермера Джона пропонує купити певну кількість молока за певною ціною. Крім того, кожен з $r$ сусідніх фермерів хоче орендувати корову за певну ціну.

Фермер Джон повинен вирішити для кожної корови, доїти її чи здати в оренду сусідньому фермеру. Допоможіть йому знайти найбільшу суму грошей, яку він може заробити за день.

Вхідні дані

Перший рядок містить три цілих числа $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5), $m (1 \leq m \leq 1 0^{5})$ m~(1 \le m \le 10^5) та $r (1 \leq r \leq 1 0^{5})$ r~(1 \le r \le 10^5). Кожен з наступних $n$ рядків містить ціле число $c_{i} (1 \leq c_{i} \leq 1 0^{6})$ c_i~(1 \le c_i \le 10^6), яке означає, що $i$ -та корова Фермера Джона може давати $c_{i}$ c_i галонів молока щодня. Кожен з наступних $m$ рядків містить два цілих числа $q_{i}$ q_i та $p_{i} (1 \leq q_{i}, p_{i} \leq 1 0^{6})$ p_i~(1 \le q_i, p_i \le 10^6), які означають, що $i$ -й магазин готовий купити до $q_{i}$ q_i галонів молока по $p_{i}$ p_i центів за галон. Зверніть увагу, що Фермер Джон може продати одному магазину будь-яку кількість молока від нуля до $q_{i}$ q_i галонів. Кожен з наступних $r$ рядків містить ціле число $r_{i} (1 \leq r_{i} \leq 1 0^{6})$ r_i~(1 \le r_i \le 10^6), яке означає, що один із сусідів Фермера Джона хоче орендувати корову за $r_{i}$ r_i центів на день.

Вихідні дані

Виведіть одне ціле число: найбільший прибуток, який Фермер Джон може отримати за день, подоївши або здавши в оренду кожну зі своїх корів. Зверніть увагу, що відповідь може не поміститися у стандартний 32-бітний цілий тип, тому вам може знадобитися більший цілий тип, наприклад "long long" у C/C++.

Приклади

Приклад 1

Примітка

Фермеру Джону слід подоїти корів $1$ та $4$ й отримати $13$ галонів молока. Йому слід повністю виконати замовлення на $10$ галонів, заробивши $250$ центів, і продати решту три галони по $15$ центів за кожен, що разом дає $295$ центів прибутку від молока.

Потім йому слід здати в оренду інших трьох корів за $250$ , $80$ та $100$ центів і заробити ще $430$ центів. (Запит на оренду за $40$ центів слід залишити невиконаним.) У підсумку виходить $725$ центів прибутку на день.