Власники рибальського судна, що веде промисел на річці Дніпро, вирішили у літньому сезоні оптимізувати свій бізнес.

Вони отримали сезонний дозвіл на лов риби в \(n\) точках русла річки на відстанях \(x_1,x_2,…,x_n\) кілометрів від гирла. При цьому в точці з номером \(i\) дозволяється виловити не більше \(a_i\) тонн риби.

Виловлену рибу можна продавати на \(m\) оптових базах, розташованих уздовж берега річки в точках на відстанях \(y_1, y_2,…, y_m\) км від гирла. При цьому база в точці номер \(𝑗\) готова цього сезону закупити не більше \(𝑏_𝑗\) тонн риби за ціною \(𝑐_𝑗\) за тонну.

Відстані від гирла до точок вилову та оптових баз вимірюються вздовж русла річки.

Судно вирушає на лов із гирла річки і має повернутися туди ж після закінчення сезону. Протягом сезону судно може довільним чином плавати вгору та вниз по річці, зупиняючись для лову чи продажу риби. Вантажопідйомність судна достатня для перевезення будь-якої кількості виловленої риби. При віддаленні від гирла судно рухається проти течії, витрачаючи на один кілометр шляху паливо вартістю \(𝑝\). При переміщенні у бік гирла судно рухається за течією і тому не витрачає палива.

За підсумками сезону прибуток за улов дорівнюватиме сумарній вартості проданої риби за вирахуванням сумарної вартості витраченого палива.

Потрібно написати програму, яка визначає максимальний прибуток, який можна отримати за сезон.

Формат вхідних даних

Перший рядок вхідних даних містить три цілих числа \(𝑛, 𝑚\) і \(𝑝\) - кількість точок лову риби, кількість оптових баз і вартість палива (\(1≤𝑛,𝑚≤500000\);\(0≤𝑝≤10^9\)).

Наступні \(𝑛\) рядків містять по два цілих числа \(𝑥_𝑖\) і \(𝑎_𝑖\) - відстань від гирла і максимальний улов для кожної точки лову риби \((0<𝑥_1<𝑥_2<⋯<𝑥_𝑛≤10^9\);\(0<𝑎_i \le 10^6)\)

Наступні \(𝑚\) рядків містять по три цілих числа \(𝑦_𝑗,𝑏_𝑗,𝑐_𝑗\) - відстань від гирла, максимальна кількість тонн риби, що закуповується, і ціна закупівлі за тонну для кожної оптової бази \((0<𝑦_1<𝑦_2<⋯< 𝑗_m ≤10^6\), \(0<𝑏_𝑗,𝑐_𝑗≤10^6\)).

Формат вихідних даних

Вихідні дані мають містити єдине ціле число — максимальний можливий прибуток.

Пояснення до прикладів

У другому прикладі оптимальними будуть такі дії. Слід доплисти до точки на відстані 6 кілометрів від гирла, витративши 600 на паливо, та виловити у ній 5 тонн риби. Після цього слід спуститися на 1 кілометр річкою до бази на відстані 5 кілометрів від гирла і продати виловлену рибу за ціною 2000 за тонну. Потім слід повернутися у гирло річки. Сумарний прибуток становитиме 9400.

Приклад вхідних даних

3 2 0
1 5
2 3
4 5
2 2 10
3 6 5

Приклад вихідних даних

50

Приклад вхідних даних

2 1 100
6 5
100 4
5 100 2000

Приклад вихідних даних

9400

Приклад вхідних даних

3 3 10
1 1
10 100
20 10
2 1000 1
11 50 50
17 50 2

Приклад вихідних даних

2441