พ่อครัว 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}{lll} 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. เขาทำขั้นตอนที่ 1 ของ JOI Curry และทำเสร็จเมื่อผ่านไป 3 นาทีนับจากเริ่มการแข่งขัน เนื่องจากไม่เกิน 6 นาที เขาจึงได้รับ 1 คะแนน
2. เขาทำขั้นตอนที่ 1 ของ IOI Donburi และทำเสร็จเมื่อผ่านไป 5 นาทีนับจากเริ่มการแข่งขัน เนื่องจากเกิน 1 นาที เขาจึงไม่ได้รับคะแนนด้านศิลปะ
3. เขาทำขั้นตอนที่ 2 ของ IOI Donburi และทำเสร็จเมื่อผ่านไป 8 นาทีนับจากเริ่มการแข่งขัน เนื่องจากไม่เกิน 8 นาที เขาจึงได้รับ 1 คะแนน
4. เขาทำขั้นตอนที่ 2 ของ JOI Curry และทำเสร็จเมื่อผ่านไป 10 นาทีนับจากเริ่มการแข่งขัน เนื่องจากไม่เกิน 11 นาที เขาจึงได้รับ 1 คะแนน
5. เขาทำขั้นตอนที่ 3 ของ IOI Donburi และทำเสร็จเมื่อผ่านไป 12 นาทีนับจากเริ่มการแข่งขัน เนื่องจากไม่เกิน 13 นาที เขาจึงได้รับ 1 คะแนน
6. เขาทำขั้นตอนที่ 4 ของ IOI Donburi และทำเสร็จเมื่อผ่านไป 13 นาทีนับจากเริ่มการแข่งขัน เนื่องจากไม่เกิน 13 นาที เขาจึงได้รับ 1 คะแนน
7. เขาทำขั้นตอนที่ 3 ของ JOI Curry และทำเสร็จเมื่อผ่านไป 15 นาทีนับจากเริ่มการแข่งขัน เนื่องจากไม่เกิน 15 นาที เขาจึงได้รับ 1 คะแนน

คะแนนด้านศิลปะรวมในกรณีนี้คือ 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