Koki Bitaro mengikuti sebuah lomba memasak. Dalam lomba ini, setiap peserta harus memasak dua hidangan: IOI Donburi dan JOI Curry.

Proses memasak IOI Donburi terdiri atas $N$ langkah. Langkah ke-$i$ ($1\le i\le N$) membutuhkan tepat $A_i$ menit. Pada awalnya, ia hanya dapat melakukan langkah pertama. Untuk melakukan langkah ke-$i$ ($2\le i\le N$), ia harus sudah menyelesaikan langkah ke-$(i-1)$.

Proses memasak JOI Curry terdiri atas $M$ langkah. Langkah ke-$j$ ($1\le j\le M$) membutuhkan tepat $B_j$ menit. Pada awalnya, ia hanya dapat melakukan langkah pertama. Untuk melakukan langkah ke-$j$ ($2\le j\le M$), ia harus sudah menyelesaikan langkah ke-$(j-1)$.

Langkah-langkah tersebut membutuhkan konsentrasi. Jadi, setelah mulai melakukan suatu langkah, ia tidak dapat melakukan langkah lain sampai langkah tersebut selesai. Di antara dua langkah, ia boleh beralih dari satu hidangan ke hidangan lainnya. Setelah lomba dimulai, ia tidak boleh beristirahat sampai kedua hidangan selesai.

Dalam lomba ini, peserta memperoleh nilai artistik sebagai berikut.

• Jika ia menyelesaikan langkah ke-$i$ ($1\le i\le N$) dalam memasak IOI Donburi paling lambat $S_i$ menit sejak lomba dimulai, ia memperoleh $P_i$ poin. Nilai $P_i$ dapat negatif.
• Jika ia menyelesaikan langkah ke-$j$ ($1\le j\le M$) dalam memasak JOI Curry paling lambat $T_j$ menit sejak lomba dimulai, ia memperoleh $Q_j$ poin. Nilai $Q_j$ dapat negatif.

Bitaro ingin memaksimalkan total nilai artistiknya.

Tulislah program yang, diberikan banyaknya langkah memasak, waktu yang dibutuhkan setiap langkah, serta informasi nilai artistik, menghitung total nilai artistik maksimum yang dapat diperoleh Bitaro.

Masukan

Bacalah data berikut dari masukan standar. Semua nilai dalam masukan berupa bilangan bulat.

$$ \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} $$

Keluaran

Tulislah satu baris ke keluaran standar yang berisi total nilai artistik maksimum yang dapat diperoleh Bitaro.

Batasan

• $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\times10^{15}$ ($1\le i\le N$).
• $1\le T_j\le 2\,000\,000\,000\,000\,000=2\times10^{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$).

Subsoal

1. (5 poin) $N\le200\,000$, $M\le200\,000$, $S_1=\cdots=S_N=T_1=\cdots=T_M$.
2. (3 poin) $N\le12$, $M\le12$, $P_i=1$ ($1\le i\le N$), $Q_j=1$ ($1\le j\le M$).
3. (7 poin) $N\le2\,000$, $M\le2\,000$, $P_i=1$ ($1\le i\le N$), $Q_j=1$ ($1\le j\le M$).
4. (39 poin) $N\le200\,000$, $M\le200\,000$, $P_i=1$ ($1\le i\le N$), $Q_j=1$ ($1\le j\le M$).
5. (11 poin) $N\le200\,000$, $M\le200\,000$, $1\le P_i$ ($1\le i\le N$), $1\le Q_j$ ($1\le j\le M$).
6. (9 poin) $1\le P_i$ ($1\le i\le N$), $1\le Q_j$ ($1\le j\le M$).
7. (17 poin) $N\le200\,000$, $M\le200\,000$.
8. (9 poin) Tidak ada batasan tambahan.

Contoh

Masukan 1

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

Keluaran 1

6

Penjelasan

Contoh masukan ini memenuhi batasan Subsoal 2.

Dalam contoh ini, Bitaro dapat melakukan langkah-langkah memasak seperti berikut, misalnya:

1. Ia melakukan langkah pertama JOI Curry dan menyelesaikannya 3 menit setelah lomba dimulai. Karena tidak melebihi 6 menit, ia memperoleh 1 poin.
2. Ia melakukan langkah pertama IOI Donburi dan menyelesaikannya 5 menit setelah lomba dimulai. Karena melebihi 1 menit, ia tidak memperoleh nilai artistik.
3. Ia melakukan langkah kedua IOI Donburi dan menyelesaikannya 8 menit setelah lomba dimulai. Karena tidak melebihi 8 menit, ia memperoleh 1 poin.
4. Ia melakukan langkah kedua JOI Curry dan menyelesaikannya 10 menit setelah lomba dimulai. Karena tidak melebihi 11 menit, ia memperoleh 1 poin.
5. Ia melakukan langkah ketiga IOI Donburi dan menyelesaikannya 12 menit setelah lomba dimulai. Karena tidak melebihi 13 menit, ia memperoleh 1 poin.
6. Ia melakukan langkah keempat IOI Donburi dan menyelesaikannya 13 menit setelah lomba dimulai. Karena tidak melebihi 13 menit, ia memperoleh 1 poin.
7. Ia melakukan langkah ketiga JOI Curry dan menyelesaikannya 15 menit setelah lomba dimulai. Karena tidak melebihi 15 menit, ia memperoleh 1 poin.

Total nilai artistik di sini adalah 6 poin. Ia tidak dapat memperoleh lebih dari 6 poin, sehingga keluarkan 6.

Masukan 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

Keluaran 2

63

Penjelasan

Contoh masukan ini memenuhi batasan Subsoal 1.

Masukan 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

Keluaran 3

99