廚師 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$ 個步驟。

這些步驟需要專注，因此一旦開始進行某個步驟，在完成之前，他不能進行其他步驟。在步驟之間，他可以從一道料理切換到另一道料理。比賽一旦開始，在完成兩道料理之前，他都不能休息。

此外，在這場比賽中，參賽者會依照以下規則獲得藝術分數。

• 如果他在比賽開始後的 $S_i$ 分鐘內完成 IOI Donburi 的第 $i$ 個烹調步驟（$1 \le i \le N$），就會獲得 $P_i$ 分。這裡 $P_i$ 的值可能為負數。
• 如果他在比賽開始後的 $T_j$ 分鐘內完成 JOI Curry 的第 $j$ 個烹調步驟（$1 \le j \le M$），就會獲得 $Q_j$ 分。這裡 $Q_j$ 的值可能為負數。

Bitaro 想要最大化他的藝術總分。

請撰寫一個程式，給定烹調步驟的數量、各步驟所需的時間，以及藝術分數的資訊，計算 Bitaro 能獲得的最大藝術總分。

輸入格式

從標準輸入讀取以下資料。輸入中的所有值都是整數。

$$ \begin{array}{ccc} 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 的第 1 個步驟，在比賽開始後 3 分鐘完成。由於這是在 6 分鐘內，因此他獲得 1 分。
2. 他進行 IOI Donburi 的第 1 個步驟，在比賽開始後 5 分鐘完成。由於這不在 1 分鐘內，因此他沒有獲得藝術分數。
3. 他進行 IOI Donburi 的第 2 個步驟，在比賽開始後 8 分鐘完成。由於這是在 8 分鐘內，因此他獲得 1 分。
4. 他進行 JOI Curry 的第 2 個步驟，在比賽開始後 10 分鐘完成。由於這是在 11 分鐘內，因此他獲得 1 分。
5. 他進行 IOI Donburi 的第 3 個步驟，在比賽開始後 12 分鐘完成。由於這是在 13 分鐘內，因此他獲得 1 分。
6. 他進行 IOI Donburi 的第 4 個步驟，在比賽開始後 13 分鐘完成。由於這是在 13 分鐘內，因此他獲得 1 分。
7. 他進行 JOI Curry 的第 3 個步驟，在比賽開始後 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