分数: 400 分
问题陈述
高桥是一家工厂的质量检验员。他正在检查 N 产品在皮带输送机上排成一排。
的 树的 i- 第一个产品 (1 \leq i \leq N) 具有质量分数 A_i 和一个重量 B_i.
给定阈值 K,任何质量分数低于 K (A_i < K) 被视为有缺陷,必须退回。质量得分为 K 或更高版本被认为是好的。
退回的有缺陷的产品将被装入箱子中以便运输。每件有缺陷的产品必须准确地放入一个盒子中,并且盒子只能包含有缺陷的产品。不使用空盒子。盒子的数量可以自由选择,但每个盒子必须满足以下条件:
- 放置在同一个盒子中的缺陷产品必须在原始排列中形成连续的段。也就是说,如果放置在盒子中的缺陷产品的位置是 l, l+1, \ldots, r (l \leq r),则来自位置的所有产品 l to r 必须是有缺陷的(中间不存在良品)。
单箱运费按其所含缺陷产品中的最大重量确定。具体来说,最大值为 盒子中的产品中的 B_i 是该盒子的运费。总运费是所有箱子的运费之和。
你被给予 Q 阈值 K_1, K_2, \ldots, K_Q。对于每个 K_j,找到退回所有缺陷产品的最低总运费。如果没有缺陷产品,总运费为 0.
每个查询都是独立的(产品的排列是共享的,但只有阈值发生变化)。
约束
- 1 \leq N
- 1 \leq Q
- N + Q \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 1 \leq K_j \leq 10^9
- 所有输入值均为整数
输入
N Q A_1 B_1 A_2 B_2 \vdots A_N B_N K_1 K_2 \vdots K_Q
- 第一行包含 N,产品数量,以及 Q,查询数量,以空格分隔。
- 从第 2 行到 (N+1)第行,给出了有关每个产品的信息。
- 的 树的 (1 + i)第行包含 A_i,质量分数 i-第一个产品,以及 B_i,其重量,以空格分隔。
- 以下 Q 行给出阈值。
- 的 树的 (N + 1 + j)第行包含 K_j,阈值 j第一个查询。
输出
打印 Q 行。
关于 j第行,打印阈值为时的最小总运费 K_j,作为整数。
示例输入 1
5 4 5 3 2 10 4 2 1 7 6 4 1 3 5 7
示例输出 1
0 17 10 10
示例输入 2
4 5 3 8 3 2 1 5 4 6 1 2 3 4 5
示例输出 2
0 5 5 8 8
示例输入 3
12 8 8 5 3 12 10 4 1 7 6 6 2 20 9 3 5 15 4 8 7 10 11 2 3 9 1 4 6 9 12 3 10 5
示例输出 3
0 48 63 56 20 27 41 56
示例输入 4
30 10 100 30 20 5 80 100 40 7 60 50 10 80 90 20 30 60 70 10 50 90 25 55 75 35 15 75 85 15 35 65 95 25 45 85 55 45 5 95 65 40 12 70 88 22 42 82 78 32 18 72 58 52 98 12 28 62 68 42 38 92 1 11 31 51 71 91 101 46 66 86
示例输出 4
0 175 574 940 656 287 100 905 778 459
示例输入 5
1 1 1 1000000000 1000000000
示例输出 5
1000000000