2772 「ROI 2017 Day 2」反物质

题目译自 ROI 2017 Day 2 T3. Антивещество

有 $n$ 种试验可以生成反物质。第 $i$ 种试验的成本为 $c_i$。你无法控制该试验会生成多少反物质，但知道该试验最少会生成 $l_i$ 克反物质，最多会生成 $r_i$ 克反物质。生成的反物质均会放在一个容器中，你可以得知容器中反物质的质量。容器中的反物质不能超过 $a$ 克。
军方想收购这些反物质，每克收购价为 $10^9$ 卢布。假设第 $i$ 种试验生成了 $t$ 克的反物质，则这次试验中你获得的利润为 $(t\times 10^9-c_i)$ 卢布。
请问，在保证安全的情况下，你「最多」可以「保证」获得多少利润（即：最坏情况下的利润不超过多少）。

对于所有数据，$1 ⩽ n ⩽ 100,$ $1 ⩽ a ⩽ 2\times 10^6,$ $1 ⩽ l_i ⩽ r_i ⩽ a,$ $1 ⩽ c_i ⩽ 100$。 | 子任务 | 分值 | $n$ | $a$ | 额外条件 | |:-:|:-:|:-:|:-:|:-:| | 1 | 10 | $n = 1$ | $1 ⩽ a ⩽ 1 000$ | 无 | | 2 |  10  | $1 ⩽ n ⩽ 10$ | $1 ⩽ a ⩽ 1 000$ | $l_i = r_i$ | | 3 | 20 | $1 ⩽ n ⩽ 10$ | $1 ⩽ a ⩽ 1 000$ | 无 | | 4 |  20  | $1 ⩽ n ⩽ 100$
（知道你会看瞎眼
提醒你一下
这里总共 60 分） | $1 ⩽ a ⩽ 5\times 10^4$ | 无 | | 5 | 4 | $1 ⩽ n ⩽ 100$
（知道你会看瞎眼
提醒你一下
这里总共 60 分） | $1 ⩽ a ⩽ 1\times 10^5$ | 无 | | 6 |  4  | $1 ⩽ n ⩽ 100$
（知道你会看瞎眼
提醒你一下
这里总共 60 分） | $1 ⩽ a ⩽ 2\times 10^5$ | 无 | | 7 | 4 | $1 ⩽ n ⩽ 100$
（知道你会看瞎眼
提醒你一下
这里总共 60 分） | $1 ⩽ a ⩽ 3\times 10^5$ | 无 | | 8 |  4  | $1 ⩽ n ⩽ 100$
（知道你会看瞎眼
提醒你一下
这里总共 60 分） | $1 ⩽ a ⩽ 4\times 10^5$ | 无 | | 9 | 4 | $1 ⩽ n ⩽ 100$
（知道你会看瞎眼
提醒你一下
这里总共 60 分） | $1 ⩽ a ⩽ 5\times 10^5$ | 无 | | 10 |  4  | $1 ⩽ n ⩽ 100$
（知道你会看瞎眼
提醒你一下
这里总共 60 分） | $1 ⩽ a ⩽ 8\times 10^5$ | 无 | | 11 | 4 | $1 ⩽ n ⩽ 100$
（知道你会看瞎眼
提醒你一下
这里总共 60 分） | $1 ⩽ a ⩽ 1.1\times 10^6$ | 无 | | 12 |  4  | $1 ⩽ n ⩽ 100$
（知道你会看瞎眼
提醒你一下
这里总共 60 分） | $1 ⩽ a ⩽ 1.4\times 10^6$ | 无 | | 13 | 4 | $1 ⩽ n ⩽ 100$
（知道你会看瞎眼
提醒你一下
这里总共 60 分） | $1 ⩽ a ⩽ 1.7\times 10^6$ | 无 | | 14 |  4  | $1 ⩽ n ⩽ 100$
（知道你会看瞎眼
提醒你一下
这里总共 60 分） | $1 ⩽ a ⩽ 2\times 10^6$ | 无 |