Description
There are N particles moving from right to left, each moving at a constant speed of one unit per second.
The position of the particles can be represented using a Cartesian coordinate system. All particles will disappear when they reach the x-axis at position 0.
TA has invented a board that can absorb the energy of these particles. The board is fixed vertically at the x-axis at position 0, but its position on the y-axis can be adjusted, and its length can also be modified before being finally fixed. Once the location and length of the board are determined, they cannot be changed.
The board can successfully absorb energy under one condition: the time interval between the absorption of the first particle and the last particle must be at least D seconds. Otherwise, the absorption will fail.
Due to cost considerations, TA hopes to minimize the length of the board. Please find the minimum length needed to satisfy the above condition. if it is not possible, please output -1.
Note: The edges of the board are also considered part of the board and can absorb particles.
If you use C++, you can add ios::sync_with_stdio(0); and cin.tie(0); to speed up input.
In HW2, you can use std library.
Input
The first line of input contains two integers, N and D.
The following N lines each represent the coordinates of a particle (xi, yi).
All inputs are integers.
Guarantee that the input of particle coordinates is sorted according to the Y-axis.
0 < = xi, yi <= 108
1 <= D <= 108
1 <= N <= 5*106
Output
Please output an integer representing the minimum length of the board.
If there is no board that meets the conditions, please output -1.