#3034. 「JOISC 2019 Day2」两道料理

内存限制:1024 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

题目译自 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

样例输出 1

6

样例说明 1

这组样例满足子任务 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

样例输出 2

63

样例说明 2

这组样例满足子任务 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

样例输出 3

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 对于任意 i\in [1,n],j\in [1,m] 的整数 i,j ,都有 S_i=T_j
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

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