codeforces#P929A. Прокат велосипедов
Прокат велосипедов
Cannot parse: NaNs error parsing time
Description
Как известно, в теплую погоду многие жители крупных городов пользуются сервисами городского велопроката. Вот и Аркадий сегодня будет добираться от школы до дома, используя городские велосипеды.
Школа и дом находятся на одной прямой улице, кроме того, на той же улице есть n точек, где можно взять велосипед в прокат или сдать его. Первый велопрокат находится в точке x1 километров вдоль улицы, второй — в точке x2 и так далее, n-й велопрокат находится в точке xn. Школа Аркадия находится в точке x1 (то есть там же, где и первый велопрокат), а дом — в точке xn (то есть там же, где и n-й велопрокат). Известно, что xi < xi + 1 для всех 1 ≤ i < n.
Согласно правилам пользования велопроката, Аркадий может брать велосипед в прокат только на ограниченное время, после этого он должен обязательно вернуть его в одной из точек велопроката, однако, он тут же может взять новый велосипед, и отсчет времени пойдет заново. Аркадий может брать не более одного велосипеда в прокат одновременно. Если Аркадий решает взять велосипед в какой-то точке проката, то он сдаёт тот велосипед, на котором он до него доехал, берёт ровно один новый велосипед и продолжает на нём своё движение.
За отведенное время, независимо от выбранного велосипеда, Аркадий успевает проехать не больше k километров вдоль улицы.
Определите, сможет ли Аркадий доехать на велосипедах от школы до дома, и если да, то какое минимальное число раз ему необходимо будет взять велосипед в прокат, включая первый велосипед? Учтите, что Аркадий не намерен сегодня ходить пешком.
В первой строке следуют два целых числа n и k (2 ≤ n ≤ 1 000, 1 ≤ k ≤ 100 000) — количество велопрокатов и максимальное расстояние, которое Аркадий может проехать на одном велосипеде.
В следующей строке следует последовательность целых чисел x1, x2, ..., xn (0 ≤ x1 < x2 < ... < xn ≤ 100 000) — координаты точек, в которых находятся велопрокаты. Гарантируется, что координаты велопрокатов заданы в порядке возрастания.
Если Аркадий не сможет добраться от школы до дома только на велосипедах, выведите -1. В противном случае, выведите минимальное количество велосипедов, которые Аркадию нужно взять в точках проката.
Input
В первой строке следуют два целых числа n и k (2 ≤ n ≤ 1 000, 1 ≤ k ≤ 100 000) — количество велопрокатов и максимальное расстояние, которое Аркадий может проехать на одном велосипеде.
В следующей строке следует последовательность целых чисел x1, x2, ..., xn (0 ≤ x1 < x2 < ... < xn ≤ 100 000) — координаты точек, в которых находятся велопрокаты. Гарантируется, что координаты велопрокатов заданы в порядке возрастания.
Output
Если Аркадий не сможет добраться от школы до дома только на велосипедах, выведите -1. В противном случае, выведите минимальное количество велосипедов, которые Аркадию нужно взять в точках проката.
Samples
4 4
3 6 8 10
2
2 9
10 20
-1
12 3
4 6 7 9 10 11 13 15 17 18 20 21
6
Note
В первом примере Аркадий должен взять первый велосипед в первом велопрокате и доехать на нём до второго велопроката. Во втором велопрокате он должен взять новый велосипед, на котором он сможет добраться до четвертого велопроката, рядом с которым и находится его дом. Поэтому Аркадию нужно всего два велосипеда, чтобы добраться от школы до дома.
Во втором примере всего два велопроката, расстояние между которыми 10. Но максимальное расстояние, которое можно проехать на одном велосипеде, равно 9. Поэтому Аркадий не сможет добраться от школы до дома только на велосипедах.