يشارك الطاهي Bitaro في مسابقة للطهي. يُطلب من المتسابق في هذه المسابقة إعداد طبقين: IOI Donburi وJOI Curry.

تتكون عملية إعداد IOI Donburi من $N$ خطوات. تستغرق الخطوة ذات الرقم $i$ ($1\le i\le N$) بالضبط $A_i$ دقيقة. في البداية، لا يمكنه تنفيذ سوى الخطوة الأولى. ولكي ينفذ الخطوة ذات الرقم $i$ ($2\le i\le N$)، يجب أن يكون قد أنهى الخطوة ذات الرقم $i-1$.

تتكون عملية إعداد JOI Curry من $M$ خطوات. تستغرق الخطوة ذات الرقم $j$ ($1\le j\le M$) بالضبط $B_j$ دقيقة. في البداية، لا يمكنه تنفيذ سوى الخطوة الأولى. ولكي ينفذ الخطوة ذات الرقم $j$ ($2\le j\le M$)، يجب أن يكون قد أنهى الخطوة ذات الرقم $j-1$.

تتطلب الخطوات التركيز، ولذلك إذا بدأ تنفيذ خطوة، فلا يمكنه تنفيذ أي خطوة أخرى حتى ينهيها. ويمكنه الانتقال من طبق إلى الآخر بين الخطوات. وبمجرد بدء المسابقة، لا يمكنه أخذ استراحة حتى يكمل الطبقين.

ويُمنح المتسابق في هذه المسابقة نقاطًا فنية على النحو التالي.

• إذا أنهى الخطوة ذات الرقم $i$ ($1\le i\le N$) من إعداد IOI Donburi خلال $S_i$ دقيقة من بدء المسابقة، يُمنح $P_i$ نقطة. وقد تكون قيمة $P_i$ سالبة.
• إذا أنهى الخطوة ذات الرقم $j$ ($1\le j\le M$) من إعداد JOI Curry خلال $T_j$ دقيقة من بدء المسابقة، يُمنح $Q_j$ نقطة. وقد تكون قيمة $Q_j$ سالبة.

يريد Bitaro تعظيم مجموع نقاطه الفنية.

اكتب برنامجًا يُعطى عدد خطوات الطهي، والوقت الذي تستغرقه، ومعلومات النقاط الفنية، ويحسب أكبر مجموع من النقاط الفنية يمكن أن يحصل عليه Bitaro.

الإدخال

اقرأ البيانات التالية من الإدخال القياسي. جميع القيم في الإدخال أعداد صحيحة.

$$ \begin{array}{l} N\ M\\ A_1\ S_1\ P_1\\ \vdots\\ A_N\ S_N\ P_N\\ B_1\ T_1\ Q_1\\ \vdots\\ B_M\ T_M\ Q_M \end{array} $$

الإخراج

اكتب سطرًا واحدًا إلى الإخراج القياسي. يجب أن يحتوي الإخراج على أكبر مجموع من النقاط الفنية يمكن أن يحصل عليه Bitaro.

القيود

• $1\le N\le 1\,000\,000$.
• $1\le M\le 1\,000\,000$.
• $1\le A_i\le 1\,000\,000\,000$ ($1\le i\le N$).
• $1\le B_j\le 1\,000\,000\,000$ ($1\le j\le M$).
• $1\le S_i\le 2\,000\,000\,000\,000\,000=2\times 10^{15}$ ($1\le i\le N$).
• $1\le T_j\le 2\,000\,000\,000\,000\,000=2\times 10^{15}$ ($1\le j\le M$).
• $-1\,000\,000\,000\le P_i\le 1\,000\,000\,000$ ($1\le i\le N$).
• $-1\,000\,000\,000\le Q_j\le 1\,000\,000\,000$ ($1\le j\le M$).

المهام الفرعية

1. (5 نقاط) $N\le 200\,000$، $M\le 200\,000$، $S_1=\cdots=S_N=T_1=\cdots=T_M$.
2. (3 نقاط) $N\le 12$، $M\le 12$، $P_i=1$ ($1\le i\le N$)، $Q_j=1$ ($1\le j\le M$).
3. (7 نقاط) $N\le 2\,000$، $M\le 2\,000$، $P_i=1$ ($1\le i\le N$)، $Q_j=1$ ($1\le j\le M$).
4. (39 نقطة) $N\le 200\,000$، $M\le 200\,000$، $P_i=1$ ($1\le i\le N$)، $Q_j=1$ ($1\le j\le M$).
5. (11 نقطة) $N\le 200\,000$، $M\le 200\,000$، $1\le P_i$ ($1\le i\le N$)، $1\le Q_j$ ($1\le j\le M$).
6. (9 نقاط) $1\le P_i$ ($1\le i\le N$)، $1\le Q_j$ ($1\le j\le M$).
7. (17 نقطة) $N\le 200\,000$، $M\le 200\,000$.
8. (9 نقاط) لا توجد قيود إضافية.

أمثلة

الإدخال 1

4 3
2 1 1
3 8 1
2 13 1
1 13 1
3 6 1
2 11 1
2 15 1

الإخراج 1

6

ملاحظة

يستوفي هذا الإدخال النموذجي قيود المهمة الفرعية 2.

في هذا المثال، يمكن لـBitaro تنفيذ خطوات الطهي كما يلي، على سبيل المثال:

1. ينفذ الخطوة الأولى من JOI Curry. وينهيها بعد 3 دقائق من بدء المسابقة. ولأن ذلك خلال 6 دقائق، يحصل على نقطة واحدة.
2. ينفذ الخطوة الأولى من IOI Donburi. وينهيها بعد 5 دقائق من بدء المسابقة. ولأن ذلك ليس خلال دقيقة واحدة، لا يحصل على أي نقاط فنية.
3. ينفذ الخطوة الثانية من IOI Donburi. وينهيها بعد 8 دقائق من بدء المسابقة. ولأن ذلك خلال 8 دقائق، يحصل على نقطة واحدة.
4. ينفذ الخطوة الثانية من JOI Curry. وينهيها بعد 10 دقائق من بدء المسابقة. ولأن ذلك خلال 11 دقيقة، يحصل على نقطة واحدة.
5. ينفذ الخطوة الثالثة من IOI Donburi. وينهيها بعد 12 دقيقة من بدء المسابقة. ولأن ذلك خلال 13 دقيقة، يحصل على نقطة واحدة.
6. ينفذ الخطوة الرابعة من IOI Donburi. وينهيها بعد 13 دقيقة من بدء المسابقة. ولأن ذلك خلال 13 دقيقة، يحصل على نقطة واحدة.
7. ينفذ الخطوة الثالثة من JOI Curry. وينهيها بعد 15 دقيقة من بدء المسابقة. ولأن ذلك خلال 15 دقيقة، يحصل على نقطة واحدة.

مجموع النقاط الفنية هنا هو 6 نقاط. ولا يمكنه الحصول على أكثر من 6 نقاط، لذا أخرج 6.

الإدخال 2

5 7
16 73 16
17 73 10
20 73 1
14 73 16
18 73 10
3 73 2
10 73 7
16 73 19
12 73 4
15 73 15
20 73 14
15 73 8

الإخراج 2

63

ملاحظة

يستوفي هذا الإدخال النموذجي قيود المهمة الفرعية 1.

الإدخال 3

9 11
86 565 58
41 469 -95
73 679 28
91 585 -78
17 513 -63
48 878 -66
66 901 59
72 983 -70
68 1432 11
42 386 -87
36 895 57
100 164 10
96 812 -6
23 961 -66
54 193 51
37 709 82
62 148 -36
28 853 22
15 44 53
77 660 -19

الإخراج 3

99