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

Execution time limit is 5 seconds

Runtime memory usage limit is 256 megabytes

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

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

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

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

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

Input

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

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

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

Output

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

Examples

Input #1

Answer #1

Scoring

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