English · Original
Chinese · Translation
Formal · Original
<center></center>It is well-known that the best decoration for a flower bed in Sweetland are vanilla muffins. Seedlings of this plant need sun to grow up. Slastyona has _m_ seedlings, and the _j_\-th seedling needs at least _k__j_ minutes of sunlight to grow up.
Most of the time it's sunny in Sweetland, but sometimes some caramel clouds come, the _i_\-th of which will appear at time moment (minute) _l__i_ and disappear at time moment _r__i_. Of course, the clouds make shadows, and the seedlings can't grow when there is at least one cloud veiling the sun.
Slastyona wants to grow up her muffins as fast as possible. She has exactly _C_ candies, which is the main currency in Sweetland.
One can dispel any cloud by paying _c__i_ candies. However, in order to comply with Sweetland's Department of Meteorology regulations, **one can't dispel more than two clouds**.
Slastyona hasn't decided yet which of the _m_ seedlings will be planted at the princess' garden, so she needs your help. For each seedling determine the earliest moment it can grow up if Slastyona won't break the law and won't spend more candies than she has. Note that each of the seedlings is considered independently.
The seedlings start to grow at time moment 0.
## Input
The first line contains two integers _n_ and _C_ (0 ≤ _n_ ≤ 3·105, 0 ≤ _C_ ≤ 109) – the number of caramel clouds and the number of candies Slastyona has.
The next _n_ lines contain three integers each: _l__i_, _r__i_, _c__i_ (0 ≤ _l__i_ < _r__i_ ≤ 109, 0 ≤ _c__i_ ≤ 109), describing one caramel cloud.
The next line contains single integer _m_ (1 ≤ _m_ ≤ 3·105) – the number of seedlings. Each of the seedlings is described with one integer _k__j_ (1 ≤ _k__j_ ≤ 109) – the required number of sunny minutes.
## Output
For each seedling print one integer – the minimum minute Slastyona can grow it up.
[samples]
## Note
Consider the first example. For each _k_ it is optimal to dispel clouds 1 and 3. Then the remaining cloud will give shadow on time segment \[1..6\]. So, intervals \[0..1\] and \[6.._inf_) are sunny.
<center></center>In the second example for _k_ = 1 it is not necessary to dispel anything, and for _k_ = 5 the best strategy is to dispel clouds 2 and 3. This adds an additional sunny segment \[4..8\], which together with \[0..1\] allows to grow up the muffin at the eight minute.
<center> </center>If the third example the two seedlings are completely different. For the first one it is necessary to dispel cloud 1 and obtain a sunny segment \[0..10\]. However, the same strategy gives answer 180 for the second seedling. Instead, we can dispel cloud 2, to make segments \[0..3\] and \[7.._inf_) sunny, and this allows up to shorten the time to 104.
众所周知，Sweetland 花坛的最佳装饰是香草纸杯蛋糕。这种植物的幼苗需要阳光才能生长。Slastyona 有 #cf_span[m] 株幼苗，第 #cf_span[j] 株幼苗至少需要 #cf_span[kj] 分钟的阳光才能生长。
Sweetland 大部分时间都是晴天，但有时会出现一些焦糖色的云，第 #cf_span[i] 朵云会在时间点（分钟）#cf_span[li] 出现，并在时间点 #cf_span[ri] 消失。当然，这些云会形成阴影，当至少有一朵云遮住太阳时，幼苗无法生长。
Slastyona 希望尽快让她的纸杯蛋糕生长。她恰好有 #cf_span[C] 颗糖果，这是 Sweetland 的主要货币。
支付 #cf_span[ci] 颗糖果可以驱散任何一朵云。然而，为了遵守 Sweetland 气象部门的规定，*最多只能驱散两朵云*。
Slastyona 尚未决定将 #cf_span[m] 株幼苗中的哪些种植在公主的花园中，因此她需要你的帮助。对于每株幼苗，请确定在 Slastyona 不违反法律且不花费超过她拥有的糖果数量的前提下，它能够生长出来的最早时刻。注意，每株幼苗是独立考虑的。
幼苗从时间点 #cf_span[0] 开始生长。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[C] #cf_span[(0 ≤ n ≤ 3·105, 0 ≤ C ≤ 109)] —— 焦糖云的数量和 Slastyona 拥有的糖果数量。
接下来的 #cf_span[n] 行每行包含三个整数：#cf_span[li, ri, ci] #cf_span[(0 ≤ li < ri ≤ 109, 0 ≤ ci ≤ 109)]，描述一朵焦糖云。
下一行包含一个整数 #cf_span[m] #cf_span[(1 ≤ m ≤ 3·105)] —— 幼苗的数量。每株幼苗由一个整数 #cf_span[kj] #cf_span[(1 ≤ kj ≤ 109)] 描述 —— 所需的阳光分钟数。
## Output
对于每株幼苗，输出一个整数 —— Slastyona 能够使其生长出来的最小分钟数。
[samples]
## Note
考虑第一个例子。对于每个 #cf_span[k]，最优策略是驱散第 #cf_span[1] 和第 #cf_span[3] 朵云。此时剩余的云会在时间区间 #cf_span[[1..6]] 内形成阴影。因此，时间区间 #cf_span[[0..1]] 和 #cf_span[[6..inf)] 是晴天。
在第二个例子中，当 #cf_span[k = 1] 时无需驱散任何云；而当 #cf_span[k = 5] 时，最佳策略是驱散第 #cf_span[2] 和第 #cf_span[3] 朵云。这会新增一个晴天区间 #cf_span[[4..8]]，与 #cf_span[[0..1]] 一起，使得纸杯蛋糕在第 8 分钟即可生长。
在第三个例子中，两株幼苗的情况完全不同。对于第一株，必须驱散第 #cf_span[1] 朵云，从而获得晴天区间 #cf_span[[0..10]]。然而，同样的策略对第二株幼苗会得到答案 #cf_span[180]。相反，我们可以驱散第 #cf_span[2] 朵云，使区间 #cf_span[[0..3]] 和 #cf_span[[7..inf)] 变为晴天，从而将所需时间缩短至 #cf_span[104]。
**Definitions**
Let $ n \in \mathbb{Z}_{\geq 0} $ be the number of caramel clouds.
Let $ C \in \mathbb{Z}_{\geq 0} $ be the number of candies available.
Let $ \mathcal{C} = \{ (l_i, r_i, c_i) \mid i \in \{1, \dots, n\} \} $ be the set of clouds, where:
- $ l_i \in \mathbb{R}_{\geq 0} $ is the start time of cloud $ i $,
- $ r_i \in \mathbb{R}_{> l_i} $ is the end time of cloud $ i $,
- $ c_i \in \mathbb{R}_{\geq 0} $ is the cost to dispel cloud $ i $.
Let $ m \in \mathbb{Z}_{>0} $ be the number of seedlings.
Let $ K = \{ k_j \in \mathbb{Z}_{>0} \mid j \in \{1, \dots, m\} \} $ be the set of required sunlight minutes for each seedling.
Let $ S \subseteq \mathcal{C} $ be the set of dispelled clouds, with $ |S| \leq 2 $ and $ \sum_{(l_i, r_i, c_i) \in S} c_i \leq C $.
Let $ U(S) = [0, \infty) \setminus \bigcup_{(l_i, r_i, c_i) \in \mathcal{C} \setminus S} (l_i, r_i) $ be the union of sunny intervals after dispelling clouds in $ S $.
Let $ T(S) = \text{measure}(U(S) \cap [0, t]) $ be the total sunny time up to time $ t $ under cloud set $ S $.
**Constraints**
1. $ 0 \leq n \leq 3 \cdot 10^5 $
2. $ 0 \leq C \leq 10^9 $
3. For each cloud $ i $: $ 0 \leq l_i < r_i \leq 10^9 $, $ 0 \leq c_i \leq 10^9 $
4. $ 1 \leq m \leq 3 \cdot 10^5 $
5. For each seedling $ j $: $ 1 \leq k_j \leq 10^9 $
6. For any dispelling set $ S $: $ |S| \leq 2 $ and $ \sum_{i \in S} c_i \leq C $
**Objective**
For each seedling $ j \in \{1, \dots, m\} $, compute:
$$
\min \left\{ t \in \mathbb{R}_{\geq 0} \;\middle|\; \exists S \subseteq \mathcal{C},\ |S| \leq 2,\ \sum_{i \in S} c_i \leq C,\ T(S) \geq k_j \right\}
$$
That is, the earliest time $ t $ such that, under some valid cloud-dispelling strategy $ S $, the total accumulated sunny time up to $ t $ is at least $ k_j $.
API Response (JSON)
{
"problem": {
"name": "E. Caramel Clouds",
"description": {
"content": "<center></center>It is well-known that the best decoration for a flower bed in Sweetland are vanilla muffins. Seed",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF833E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "<center></center>It is well-known that the best decoration for a flower bed in Sweetland are vanilla muffins. Seed...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "众所周知，Sweetland 花坛的最佳装饰是香草纸杯蛋糕。这种植物的幼苗需要阳光才能生长。Slastyona 有 #cf_span[m] 株幼苗，第 #cf_span[j] 株幼苗至少需要 #cf_span[kj] 分钟的阳光才能生长。\n\nSweetland 大部分时间都是晴天，但有时会出现一些焦糖色的云，第 #cf_span[i] 朵云会在时间点（分钟）#cf_span[li] 出现，并在时间...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}_{\\geq 0} $ be the number of caramel clouds. \nLet $ C \\in \\mathbb{Z}_{\\geq 0} $ be the number of candies available. \nLet $ \\mathcal{C} = \\{ (l_i, r_i, c_i) \\m...",
"is_translate": false,
"language": "Formal"
}
]
}