题目描述

题目译自 JOISC 2019 Day2 T2「ふたつの料理 / Two Dishes」

厨师比太郎正在参加一个厨艺比赛。在这场比赛中参赛者要烹饪两道料理：IOI 盖饭和 JOI 咖喱。

IOI 盖饭的烹饪过程中需要 $N$ 个步骤。第 $i (1\le i\le N)$ 步的用时是 $A_i$ 分钟，最初他只能进行第 $1$ 步，想要进行第 $i (2\le i \le N)$ 步的条件是已经完成了第 $i - 1$ 步。

JOI 咖喱的烹饪过程中需要 $M$ 个步骤。第 $j (1\le j\le M)$ 步的用时是 $B_j$ 分钟，最初他只能进行第 $1$ 步，想要进行第 $j (2\le j \le M)$ 步的条件是已经完成了第 $j - 1$ 步。

做料理过程中需要专心致志，所以当他开始进行一个步骤时，就不能中断。当完成了一个步骤，他也可以选择进行另一道料理的下一个步骤。比赛开始后，在两道料理都完成之前，他不能停下来休息。

在这场比赛中，参赛者会按照接下来的方式得到艺术感的打分：

• 如果他在比赛的前 $S_i (1\le i \le N)$ 分钟内完成了 IOI 盖饭的第 $i$ 个步骤，那么从中他会得到 $P_i$ 点的分数，分数有可能是负的。
• 如果他在比赛的前 $T_j (1\le j \le M)$ 分钟内完成了 JOI 咖喱的第 $j$ 个步骤，那么从中他会得到 $Q_j$ 点的分数，分数有可能是负的。

请你帮助比太郎设计做料理过程，最大化他做料理的艺术感评分。

输入格式

从标准输入中读取数据。

第一行两个整数 $N,M$。

接下来 $N$ 行，每行三个整数 $A_i,S_i,P_i$。

接下来 $M$ 行，每行三个整数 $B_j,T_j,Q_j$。

输出格式

输出数据到标准输出中。

一个整数，表示比太郎能得到的最高艺术感评分。

样例 1

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

6

这组样例满足子任务 2 的限制。

比太郎可以按照此方案进行烹饪：

1. 进行 JOI 咖喱的第 $1$ 个步骤，完成时已经距离比赛开始 $3$ 分钟，还在 $6$ 分钟内，他得到 $1$ 分。
2. 进行 IOI 盖饭的第 $1$ 个步骤，完成时已经距离比赛开始 $5$ 分钟，不在 $1$ 分钟内，他没有得分。
3. 进行 IOI 盖饭的第 $2$ 个步骤，完成时已经距离比赛开始 $8$ 分钟，还在 $8$ 分钟内，他得到 $1$ 分。
4. 进行 JOI 咖喱的第 $2$ 个步骤，完成时已经距离比赛开始 $10$ 分钟，还在 $11$ 分钟内，他得到 $1$ 分。
5. 进行 IOI 盖饭的第 $3$ 个步骤，完成时已经距离比赛开始 $12$ 分钟，还在 $13$ 分钟内，他得到 $1$ 分。
6. 进行 IOI 盖饭的第 $4$ 个步骤，完成时已经距离比赛开始 $13$ 分钟，还在 $13$ 分钟内，他得到 $1$ 分。
7. 进行 JOI 咖喱的第 $3$ 个步骤，完成时已经距离比赛开始 $15$ 分钟，还在 $15$ 分钟内，他得到 $1$ 分。

比太郎总共得到 $6$ 分，他无法得到更高的分数。

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

63

这组样例满足子任务 1 的限制。

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

99

数据范围与提示

限制

• $1\le N, M\le 10^6$
• $1\le A_i, B_j \le 10^9 (1\le i\le N, 1\le j\le M)$
• $1\le S_i, T_j\le 2\times 10^{15} (1\le i\le N, 1\le j\le M)$
• $|P_i|, |Q_j| \le 10^9(1\le i\le N, 1\le j\le M)$

子任务

注：子任务中未填部分限制同「限制」中所示。