中心镇市长想要对中央街进行现代化改造,在此问题中以 $$$(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$$$ 被覆盖,但这并不重要。