厨师 Bitaro 正在参加一场烹饪比赛。在这场比赛中，选手需要制作两道菜：IOI 盖饭和 JOI 咖喱。

IOI 盖饭的烹饪过程包含 $N$ 个步骤。第 $i$ 个步骤（$1 \le i \le N$）恰好需要 $A_i$ 分钟。最初，他只能进行第一个步骤。要进行第 $i$ 个步骤（$2 \le i \le N$），他必须已经完成了第 $(i-1)$ 个步骤。

JOI 咖喱的烹饪过程包含 $M$ 个步骤。第 $j$ 个步骤（$1 \le j \le M$）恰好需要 $B_j$ 分钟。最初，他只能进行第一个步骤。要进行第 $j$ 个步骤（$2 \le j \le M$），他必须已经完成了第 $(j-1)$ 个步骤。

烹饪步骤需要集中注意力，因此一旦他开始执行某个步骤，在完成该步骤之前，他不能执行其他步骤。在步骤之间，他可以在两道菜之间切换。比赛一旦开始，在完成两道菜之前，他不能休息。

顺便提一下，在这场比赛中，选手可以获得如下艺术分： 如果他在比赛开始后的 $S_i$ 分钟内完成了 IOI 盖饭的第 $i$ 个步骤（$1 \le i \le N$），他将获得 $P_i$ 分。这里，$P_i$ 的值可能是负数。 如果他在比赛开始后的 $T_j$ 分钟内完成了 JOI 咖喱的第 $j$ 个步骤（$1 \le j \le M$），他将获得 $Q_j$ 分。这里，$Q_j$ 的值可能是负数。

Bitaro 想要最大化他的总艺术分。

请编写一个程序，在给定烹饪步骤数量、所需时间以及艺术分信息的情况下，计算 Bitaro 可以获得的最大总艺术分。

输入格式

从标准输入读取以下数据。所有输入值均为整数。

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

输出格式

输出一行到标准输出，包含 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 \times 10^{15}$ ($1 \le i \le N$)
• $1 \le T_j \le 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 = \dots = S_N = T_1 = \dots = 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

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

样例输入 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