Məsələlər
Вороги та шаблі
Вороги та шаблі
Козак Вус приїхав на Січ, щоб відвідати знайомого, який у своїй майстерні почав кувати шаблі. Знайомий вже встиг викувати $n$ шабель, при чому $i$-та шабля має два параметри --- довжину та гостроту, що позначаються як $a_i$ та $b_i$ відповідно, а також $i$-та шабля коштує $cost_i$ карбованців.
Нещодавно на Січі з'явилось $m$ ворогів. Отаман запропонував винагороду за кожного з них --- спіймавши $j$-го ворога, можна отримати винагороду в $profit_j$ карбованців. Але різні вороги також мають різні параметри броні --- товщину та міцність, що позначаються як $c_j$ та $d_j$ відповідно.
Щоб спіймати ворога, необхідно пробити його броню. Для цього потрібна шабля, довжина якої не менша, ніж товщина броні, і гострота якої не менша, ніж міцність броні. Формально, за допомогою $i$-ї шаблі можна спіймати $j$-го ворога, якщо виконуються обидві умови --- $a_i \geq c_j$ та $b_i \geq d_j$.
Козак Вус хоче дізнатись, яким може бути максимальне число карбованців, які він може заробити, щоб вирішити, чи варто займатись такою небезпечною справою, і просить вас допомогти.
Зверніть увагу, що на Січі можна брати карбованці в кредит, тобто Козак Вус може мати від'ємне число карбованців у деякий момент часу. Також Козак Вус може використовувати одну шаблю, щоб спіймати кількох ворогів.
\InputFile
Перший рядок містить два цілі числа $n$ і $m$ ($1 \leq n,m \leq 10^6$) --- кількість шабель та ворогів відповідно.
Наступні $n$ рядків містять по три цілі числа $a_i$, $b_i$ та $cost_i$ ($0 \leq a_i, b_i, cost_i \leq 10^9$) --- довжина, гострота та ціна $i$-ї шаблі.
Наступні $m$ рядків містять по три цілі числа $c_j$, $d_j$ та $profit_j$ ($0 \leq c_j, d_j, profit_j \leq 10^9$) --- товщина і міцність броні $j$-го ворога та винагорода за нього.
\OutputFile
Виведіть єдине ціле число - максимальна кількість карбованців, яку може заробити Козак Вус.
\Scoring
\begin{enumerate}
\item ($13$ балів): для будь-яких двох \textbf{ворогів} $(i,j)$, де $i\ne j$, або $c_i>c_j$, або $d_i>d_j$, тобто не існує ворога, який має обидва параметри броні не гірші за іншого; $n, m \leq 5\,000$;
\item ($10$ балів): для будь-яких двох \textbf{ворогів} $(i,j)$, де $i\ne j$, або $c_i>c_j$, або $d_i>d_j$, тобто не існує ворога, який має обидва параметри броні не гірші за іншого; $n, m \leq 10^5$;
\item ($13$ балів): для будь-яких двох \textbf{шабель} $(i,j)$, де $i\ne j$, або $a_i>a_j$, або $b_i>b_j$, тобто не існує шаблі, яка має обидва параметри атаки не гірші за іншу; $n, m \leq 5\,000$;
\item ($10$ балів): для будь-яких двох \textbf{шабель} $(i,j)$, де $i\ne j$, або $a_i>a_j$, або $b_i>b_j$, тобто не існує шаблі, яка має обидва параметри атаки не гірші за іншу; $n, m \leq 10^5$;
\item ($14$ балів): $n,m \leq 5000$;
\item ($23$ бали): $n,m \leq 10^5$;
\item ($17$ балів): без додаткових обмежень.
\end{enumerate}
Giriş verilənləri #1
2 2 2 4 10 4 5 15 1 3 50 3 1 100
Çıxış verilənləri #1
135