#P18927. [2026多校联测]烹饪比赛

[2026多校联测]烹饪比赛

烹饪比赛

题目描述

lbw 正在参加一场烹饪比赛。在本比赛中,参赛者需要制作两道菜:A 盖饭和 B 咖喱。

A 盖饭的烹饪过程包含 NN 个步骤。第 ii 步(1≤i≤N1\le i\le N)恰好需要 AiA_i 分钟。初始时,他只能执行第一步。要执行第 ii 步(2≤i≤N2\le i\le N),他必须先完成第 (i−1)(i-1) 步。

B 咖喱的烹饪过程包含 MM 个步骤。第 jj 步(1≤j≤M1\le j\le M)恰好需要 BjB_j 分钟。初始时,他只能执行第一步。要执行第 jj 步(2≤j≤M2\le j\le M),他必须先完成第 (j−1)(j-1) 步。

步骤需要集中精力,因此一旦他开始执行某个步骤,就必须完成该步骤后才能执行其他步骤。在步骤之间,他可以从一道菜切换到另一道菜。比赛开始后,他必须完成两道菜后才能休息。

顺便说明,在本比赛中,参赛者将获得如下艺术评分:

  • 若他在比赛开始后 SiS_i 分钟内完成 A 盖饭的第 ii 步(1≤i≤N1\le i\le N),则获得 PiP_i 分。此处,PiP_i 的值可能为负数。
  • 若他在比赛开始后 TjT_j 分钟内完成 B 咖喱的第 jj 步(1≤j≤M1\le j\le M),则获得 QjQ_j 分。此处,QjQ_j 的值可能为负数。

lbw 希望最大化他的总艺术评分。

编写一个程序,在给定烹饪步骤数量、各步骤所需时间以及艺术评分信息后,计算 lbw 能获得的最大总艺术评分。

输入格式

从标准输入读取以下数据。输入中的所有数值均为整数。

N M
A_1 S_1 P_1
⋮
A_N S_N P_N
B_1 T_1 Q_1
⋮
B_M T_M Q_M

输出格式

输出数据到标准输出中。一个整数,表示 lbw 能得到的最大总艺术评分。

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

输入:

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

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

本样例输入满足子任务 2 的约束条件。在本样例输入中,lbw 可按如下方式执行烹饪步骤,例如:

  1. 他执行 B 咖喱的第 1 步。他在比赛开始后 3 分钟完成。由于该时间在 6 分钟内,他获得 1 分。
  2. 他执行 A 盖饭的第 1 步。他在比赛开始后 5 分钟完成。由于该时间不在 1 分钟内,他未获得艺术评分。
  3. 他执行 A 盖饭的第 2 步。他在比赛开始后 8 分钟完成。由于该时间在 8 分钟内,他获得 1 分。
  4. 他执行 B 咖喱的第 2 步。他在比赛开始后 10 分钟完成。由于该时间在 11 分钟内,他获得 1 分。
  5. 他执行 A 盖饭的第 3 步。他在比赛开始后 12 分钟完成。由于该时间在 13 分钟内,他获得 1 分。
  6. 他执行 A 盖饭的第 4 步。他在比赛开始后 13 分钟完成。由于该时间在 13 分钟内,他获得 1 分。
  7. 他执行 B 咖喱的第 3 步。他在比赛开始后 15 分钟完成。由于该时间在 15 分钟内,他获得 1 分。

此处,总艺术评分为 6 分。他无法获得超过 6 分,因此输出 6。

数据范围

  • 1≤N≤1 000 0001\le N\le 1\,000\,000。
  • 1≤M≤1 000 0001\le M\le 1\,000\,000。
  • 1≤Ai≤1 000 000 0001\le A_i\le 1\,000\,000\,000(1≤i≤N1\le i\le N)。
  • 1≤Bj≤1 000 000 0001\le B_j\le 1\,000\,000\,000(1≤j≤M1\le j\le M)。
  • $1\le S_i\le 2\,000\,000\,000\,000\,000=2\times 10^{15}$(1≤i≤N1\le i\le N)。
  • $1\le T_j\le 2\,000\,000\,000\,000\,000=2\times 10^{15}$(1≤j≤M1\le j\le M)。
  • −1 000 000 000≤Pi≤1 000 000 000-1\,000\,000\,000\le P_i\le 1\,000\,000\,000(1≤i≤N1\le i\le N)。
  • −1 000 000 000≤Qj≤1 000 000 000-1\,000\,000\,000\le Q_j\le 1\,000\,000\,000(1≤j≤M1\le j\le M)。

子任务

  1. (5 分)N≤200 000N\le 200\,000,M≤200 000M\le 200\,000,S1=⋯=SN=T1=⋯=TMS_1=\cdots=S_N=T_1=\cdots=T_M。
  2. (3 分)N≤12N\le 12,M≤12M\le 12,Pi=1P_i=1(1≤i≤N1\le i\le N),Qj=1Q_j=1(1≤j≤M1\le j\le M)。
  3. (7 分)N≤2 000N\le 2\,000,M≤2 000M\le 2\,000,Pi=1P_i=1(1≤i≤N1\le i\le N),Qj=1Q_j=1(1≤j≤M1\le j\le M)。
  4. (39 分)N≤200 000N\le 200\,000,M≤200 000M\le 200\,000,Pi=1P_i=1(1≤i≤N1\le i\le N),Qj=1Q_j=1(1≤j≤M1\le j\le M)。
  5. (11 分)N≤200 000N\le 200\,000,M≤200 000M\le 200\,000,1≤Pi1\le P_i(1≤i≤N1\le i\le N),1≤Qj1\le Q_j(1≤j≤M1\le j\le M)。
  6. (9 分)1≤Pi1\le P_i(1≤i≤N1\le i\le N),1≤Qj1\le Q_j(1≤j≤M1\le j\le M)。
  7. (17 分)N≤200 000N\le 200\,000,M≤200 000M\le 200\,000。
  8. (9 分)无额外约束。