← 返回题目列表

AtCoder · awc0078_d

D. 产品退货

中文机器翻译题面 查看原题

分数: 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