Козак Вус приїхав на Січ, щоб відвідати знайомого, який у своїй майстерні почав кувати шаблі. Знайомий вже встиг викувати n шабель, при чому i-та шабля має два параметри — довжину та гостроту, що позначаються як ai та bi відповідно, а також i-та шабля коштує costi карбованців.
Нещодавно на Січі з'явилось m ворогів. Отаман запропонував винагороду за кожного з них — спіймавши j-го ворога, можна отримати винагороду в profitj карбованців. Але різні вороги також мають різні параметри броні — товщину та міцність, що позначаються як cj та dj відповідно.
Щоб спіймати ворога, необхідно пробити його броню. Для цього потрібна шабля, довжина якої не менша, ніж товщина броні, і гострота якої не менша, ніж міцність броні. Формально, за допомогою i-ї шаблі можна спіймати j-го ворога, якщо виконуються обидві умови — ai≥cj та bi≥dj.
Козак Вус хоче дізнатись, яким може бути максимальне число карбованців, які він може заробити, щоб вирішити, чи варто займатись такою небезпечною справою, і просить вас допомогти.
Зверніть увагу, що на Січі можна брати карбованці в кредит, тобто Козак Вус може мати від'ємне число карбованців у деякий момент часу. Також Козак Вус може використовувати одну шаблю, щоб спіймати кількох ворогів.
Перший рядок містить два цілі числа n і m (1≤n,m≤106) — кількість шабель та ворогів відповідно.
Наступні n рядків містять по три цілі числа ai, bi та costi (0≤ai,bi,costi≤109) — довжина, гострота та ціна i-ї шаблі.
Наступні m рядків містять по три цілі числа cj, dj та profitj (0≤cj,dj,profitj≤109) — товщина і міцність броні j-го ворога та винагорода за нього.
Виведіть єдине ціле число - максимальна кількість карбованців, яку може заробити Козак Вус.
(13 балів): для будь-яких двох ворогів (i,j), де i=j, або ci>cj, або di>dj, тобто не існує ворога, який має обидва параметри броні не гірші за іншого; n,m≤5000;
(10 балів): для будь-яких двох ворогів (i,j), де i=j, або ci>cj, або di>dj, тобто не існує ворога, який має обидва параметри броні не гірші за іншого; n,m≤105;
(13 балів): для будь-яких двох шабель (i,j), де i=j, або ai>aj, або bi>bj, тобто не існує шаблі, яка має обидва параметри атаки не гірші за іншу; n,m≤5000;
(10 балів): для будь-яких двох шабель (i,j), де i=j, або ai>aj, або bi>bj, тобто не існує шаблі, яка має обидва параметри атаки не гірші за іншу; n,m≤105;
(14 балів): n,m≤5000;
(23 бали): n,m≤105;
(17 балів): без додаткових обмежень.