题目描述

题目译自 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 分，他无法得到更高的分数。

---

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

输出

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

输出

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

子任务

Subtask	分值	$N, M\le$	$P_i,Q_j$	特殊限制
1	5	$2\times 10^5$		$S_1=\ldots=S_N=T_1=\ldots=T_M$
2	3	12	$=1$
3	7	$2\times 10^3$
4	39	$2\times 10^5$
5	11		$\ge 1$
6	9
7	17	$2\times 10^5$
8	9

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