← 返回题目列表

Codeforces · 833/E

E. 焦糖云

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

众所周知,甜地花坛最好的装饰是香草松饼。这种植物的幼苗需要阳光才能生长。 Slastyona 有 m 个幼苗,第 j 个幼苗至少需要 kj 分钟的阳光才能长大。

Sweetland大部分时间都是晴天,但有时会出现一些焦糖云,其中第i个焦糖云会在时刻(分)li出现并在时刻ri消失。当然,云会产生阴影,当至少有一朵云遮住太阳时,幼苗就无法生长。

Slastyona 希望她的松饼尽快长大。她正好有C糖果,这是甜蜜之地的主要货币。

支付 ci 糖果即可驱散任何乌云。不过,为了遵守斯威特兰气象局的规定,一片云不能驱散超过两片云。

Slastyona 尚未决定将哪一棵树苗种植在公主的花园里,所以她需要你的帮助。对于每棵幼苗,如果斯拉斯蒂奥娜不违法并且不花费比她拥有的更多的糖果,则确定它最早可以长大的时刻。请注意,每个幼苗都是独立考虑的。

幼苗在时刻 0 开始生长。

输入

第一行包含两个整数 n 和 C (0 ≤ n ≤ 3·105, 0 ≤ C ≤ 109) – 焦糖云的数量和 Slastyona 拥有的糖果数量。

接下来的 n 行每行包含三个整数:li, ri, ci (0 ≤ li < ri ≤ 109, 0 ≤ ci ≤ 109),描述一个焦糖云。

下一行包含单个整数 m (1 ≤ m ≤ 3·105) – 幼苗的数量。每棵幼苗都用一个整数 kj (1 ≤ kj ≤ 109) 来描述——所需的晴天分钟数。

输出

为每一棵幼苗打印一个整数——Slastyona 可以让它长大的最短分钟。

示例

输入 #1

3 5
1 7 1
1 6 2
1 7 1
3
7
2
5

输出 #1

12
7
10

输入 #2

3 15
1 4 17
2 8 6
4 8 9
2
5
1

输出 #2

8
1

输入 #3

2 10
3 7 9
10 90 10
2
10
100

输出 #3

10
104

注意

考虑第一个例子。对于每个 k,最好消除云 1 和 3。然后剩余的云将在时间段 [1..6] 上产生阴影。因此,间隔 [0..1] 和 [6..inf) 都是晴天。

在第二个示例中,k = 1 时,无需驱散任何东西,而 k = 5 时,最佳策略是驱散云 2 和 3。这会添加一个额外的阳光片段 [4..8],与 [0..1] 一起允许松饼在第 8 分钟长大。

如果是第三个例子,则两株幼苗完全不同。对于第一个,需要驱散云 1 并获得晴朗的部分 [0..10]。然而,同样的策略对于第二棵树苗给出了答案 180。相反,我们可以驱散云 2,使段 [0..3] 和 [7..inf) 晴朗,这样最多可以将时间缩短到 104。