← 返回题目列表

Codeforces · 1253/E

E. 天线覆盖范围

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

中心镇市长想要对中央街进行现代化改造,在此问题中以 $$$(Ox)$$$ 轴表示。

在这条街上,有$$$n$$$天线,编号从$$$1$$$到$$$n$$$。第 $$$i$$$ 天线位于位置 $$$x_i$$$ 上,初始范围为 $$$s_i$$$:它覆盖区间 $$$[x_i - s_i; 内的所有整数位置; x_i + s_i]$$$。

可以将任何天线的范围增加 $$$1$$$,此操作需要花费 $$$1$$$ 硬币。我们可以根据需要多次执行此操作(如果需要,可以在同一天线上执行多次)。

为了使街道现代化,我们需要使从 $$$1$$$ 到 $$$m$$$(含)的所有整数位置至少被一根天线覆盖。请注意,它被授权补仓 $$$[1; 之外的头寸m]$$$,即使不需要。

实现这一现代化至少需要多少硬币?

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 80$$$ 和 $$$n \le m \le 100\ 000$$$)。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含两个整数 $$$x_i$$$ 和 $$$s_i$$$($$$1 \le x_i \le m$$$ 和 $$$0 \le s_i \le m$$$)。

在每个位置上,至多有一个天线(值 $$$x_i$$$ 成对不同)。

输出

您必须输出一个整数:使从 $$$1$$$ 到 $$$m$$$(含)的所有整数位置被至少一根天线覆盖所需的最小硬币数量。

示例

输入 #1

3 595
43 2
300 4
554 10

输出 #1

281

输入 #2

1 1
1 1

输出 #2

0

输入 #3

2 50
20 0
3 1

输出 #3

30

输入#4

5 240
13 0
50 25
60 5
155 70
165 70

输出#4

26

注意

在第一个示例中,这是一个可能的策略:

- 将第一个天线的范围增加$$$40$$$,使其变为$$$2 + 40 = 42$$$。该天线将覆盖区间 $$$[43 - 42; 43 + 42]$$$ 即 $$$[1; 85]$$$
- 将第二个天线的范围增加$$$210$$$,使其变为$$$4 + 210 = 214$$$。该天线将覆盖区间 $$$[300 - 214; 300 + 214]$$$,即$$$[86;第514章
- 将第三根天线的范围增加$$$31$$$,使其变为$$$10 + 31 = 41$$$。该天线将覆盖区间 $$$[554 - 41; 554 + 41]$$$,即$$$[513;第595章

总成本为 $$$40 + 210 + 31 = 281$$$。我们可以证明,这是使从 $$$1$$$ 到 $$$595$$$ 的所有位置被至少一根天线覆盖所需的最低成本。

请注意,位置 $$$513$$$ 和 $$$514$$$ 在此解决方案中被两个不同的天线覆盖,但这并不重要。

—

在第二个示例中,第一根天线已经覆盖了区间 $$$[0; 2]$$$ 所以我们无事可做。

请注意,我们需要覆盖的唯一位置是 $$$1$$$ 位置;位置 $$$0$$$ 和 $$$2$$$ 被覆盖,但这并不重要。