306806: CF1253E. Antenna Coverage
Memory Limit:256 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Antenna Coverage
题意翻译
街道上有$n$个天线。第$i$个天线的位置为$x_i$,以及一个范围值$s_i$;第$i$个天线的覆盖范围是$[x_i-s_i,x_i+s_i]$。 每次操作,你可以花费$1$代价,使得第$i$个天线的$s_i$增加一。每个天线都可以进行多次操作。现在请问你最少需要花费多少代价,使$[1,m]$编号内的每一个位置都被至少一个天线覆盖。题目描述
The mayor of the Central Town wants to modernize Central Street, represented in this problem by the $ (Ox) $ axis. On this street, there are $ n $ antennas, numbered from $ 1 $ to $ n $ . The $ i $ -th antenna lies on the position $ x_i $ and has an initial scope of $ s_i $ : it covers all integer positions inside the interval $ [x_i - s_i; x_i + s_i] $ . It is possible to increment the scope of any antenna by $ 1 $ , this operation costs $ 1 $ coin. We can do this operation as much as we want (multiple times on the same antenna if we want). To modernize the street, we need to make all integer positions from $ 1 $ to $ m $ inclusive covered by at least one antenna. Note that it is authorized to cover positions outside $ [1; m] $ , even if it's not required. What is the minimum amount of coins needed to achieve this modernization?输入输出格式
输入格式
The first line contains two integers $ n $ and $ m $ ( $ 1 \le n \le 80 $ and $ n \le m \le 100\ 000 $ ). The $ i $ -th of the next $ n $ lines contains two integers $ x_i $ and $ s_i $ ( $ 1 \le x_i \le m $ and $ 0 \le s_i \le m $ ). On each position, there is at most one antenna (values $ x_i $ are pairwise distinct).
输出格式
You have to output a single integer: the minimum amount of coins required to make all integer positions from $ 1 $ to $ m $ inclusive covered by at least one antenna.
输入输出样例
输入样例 #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