Вороги та шаблі#10451

Вороги та шаблі

5 секунд

256 мегабайтів

Легка

Козак Вус приїхав на Січ, щоб відвідати знайомого, який у своїй майстерні почав кувати шаблі. Знайомий вже встиг викувати $n$ шабель, при чому $i$ -та шабля має два параметри — довжину та гостроту, що позначаються як $a_{i}$ a_i та $b_{i}$ b_i відповідно, а також $i$ -та шабля коштує $cos t_{i}$ cost_i карбованців.

Нещодавно на Січі з'явилось $m$ ворогів. Отаман запропонував винагороду за кожного з них — спіймавши $j$ -го ворога, можна отримати винагороду в $p r o f i t_{j}$ profit_j карбованців. Але різні вороги також мають різні параметри броні — товщину та міцність, що позначаються як $c_{j}$ c_j та $d_{j}$ d_j відповідно.

Щоб спіймати ворога, необхідно пробити його броню. Для цього потрібна шабля, довжина якої не менша, ніж товщина броні, і гострота якої не менша, ніж міцність броні. Формально, за допомогою $i$ -ї шаблі можна спіймати $j$ -го ворога, якщо виконуються обидві умови — $a_{i} \geq c_{j}$ a_i \geq c_j та $b_{i} \geq d_{j}$ b_i \geq d_j.

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

Зверніть увагу, що на Січі можна брати карбованці в кредит, тобто Козак Вус може мати від'ємне число карбованців у деякий момент часу. Також Козак Вус може використовувати одну шаблю, щоб спіймати кількох ворогів.

Вхідні дані

Перший рядок містить два цілі числа $n$ і $m$ ( $1 \leq n, m \leq 1 0^{6}$ 1 \leq n,m \leq 10^6) — кількість шабель та ворогів відповідно.

Наступні $n$ рядків містять по три цілі числа $a_{i}$ a_i, $b_{i}$ b_i та $cos t_{i}$ cost_i ( $0 \leq a_{i}, b_{i}, cos t_{i} \leq 1 0^{9}$ 0 \leq a_i, b_i, cost_i \leq 10^9) — довжина, гострота та ціна $i$ -ї шаблі.

Наступні $m$ рядків містять по три цілі числа $c_{j}$ c_j, $d_{j}$ d_j та $p r o f i t_{j}$ profit_j ( $0 \leq c_{j}, d_{j}, p r o f i t_{j} \leq 1 0^{9}$ 0 \leq c_j, d_j, profit_j \leq 10^9) — товщина і міцність броні $j$ -го ворога та винагорода за нього.

Вихідні дані

Виведіть єдине ціле число - максимальна кількість карбованців, яку може заробити Козак Вус.

Приклади

Приклад 1

Оцінювання

( $13$ балів): для будь-яких двох ворогів $(i, j)$ , де $i \neq = j$ i\ne j, або $c_{i} > c_{j}$ c_i>c_j, або $d_{i} > d_{j}$ d_i>d_j, тобто не існує ворога, який має обидва параметри броні не гірші за іншого; $n, m \leq 5000$ n, m \leq 5\,000;
( $10$ балів): для будь-яких двох ворогів $(i, j)$ , де $i \neq = j$ i\ne j, або $c_{i} > c_{j}$ c_i>c_j, або $d_{i} > d_{j}$ d_i>d_j, тобто не існує ворога, який має обидва параметри броні не гірші за іншого; $n, m \leq 1 0^{5}$ n, m \leq 10^5;
( $13$ балів): для будь-яких двох шабель $(i, j)$ , де $i \neq = j$ i\ne j, або $a_{i} > a_{j}$ a_i>a_j, або $b_{i} > b_{j}$ b_i>b_j, тобто не існує шаблі, яка має обидва параметри атаки не гірші за іншу; $n, m \leq 5000$ n, m \leq 5\,000;
( $10$ балів): для будь-яких двох шабель $(i, j)$ , де $i \neq = j$ i\ne j, або $a_{i} > a_{j}$ a_i>a_j, або $b_{i} > b_{j}$ b_i>b_j, тобто не існує шаблі, яка має обидва параметри атаки не гірші за іншу; $n, m \leq 1 0^{5}$ n, m \leq 10^5;
( $14$ балів): $n, m \leq 5000$ n,m \leq 5000;
( $23$ бали): $n, m \leq 1 0^{5}$ n,m \leq 10^5;
( $17$ балів): без додаткових обмежень.