Задача D. Лара Крофт и подвесной мост

Автор:Д. Заборцева, В. Пальчевский   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:512 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Расхитительница гробниц Лара Крофт стоит на левом краю ущелья. Она хочет перебраться на правую сторону чтобы исследовать древний храм. Для этого ей нужно без остановок пробежать вперёд по подвесному мосту длиной N досок.

В ущелье бушует сильный ветер, поэтому каждую секунду где-то может упасть одна или несколько досок, либо не упасть ни одной. Каждую секунду Лара должна прыгнуть вперёд на любое количество досок от 1 до K. Если доска, на которую собирается прыгнуть Лара, обвалится в ту же секунду, то приключение героини окончено.

Оракул подсказал Ларе N чисел xi — номера секунд, в который обвалится i-ая доска подвесного моста. В нулевую секунду Лара стоит на левом краю ущелья.

Необходимо определить, сможет ли Лара перебраться на правую сторону ущелья и если да, то за сколько секунд.

Формат входного файла

Первая строка входного файла содержится целые числа N и K.

Вторая строка содержит N целых чисел xi.

Формат выходного файла

Выходной файл должен содержать единственное целое число — минимальное количество секунд, за которые Лара преодолеет мост и окажется на правой стороне ущелья.

Если Лара не сможет добраться до другой стороны ущелья, выведите  − 1.

Ограничения

0 ≤ K ≤ 100

1 ≤ N ≤ 105

0 ≤ xi ≤ 2 ⋅ 105

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
6 1
1 1 4 5 8 0
-1
2
10 2
4 2 2 5 10 5 4 9 0 10
6

0.092s 0.009s 13