题目背景

本题测试数据较大，可能需要 1-1.5 分钟的时间加载测试数据。

题目描述

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 能获得的最大总艺术评分。

4 3
2 1 1
3 8 1
2 13 1
1 13 1
3 6 1
2 11 1
2 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

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 解释

本样例输入满足子任务 2 的约束条件。

在本样例输入中，Bitaro 可按如下方式执行烹饪步骤，例如：

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 分。他无法获得超过 6 分，因此输出 6。

数据范围

• $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 分）无额外约束。

翻译由 Qwen3-235B 完成