P14344 [JOISC 2019] 两道料理 / Two Dishes

本题测试数据较大，可能需要 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 能获得的最大总艺术评分。

### 样例 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 完成