Задача G. Отпуск программиста ≡

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

После многих лет беспрерывной работы программист собрался наконец-то взять N дней отпуска. Во время отпуска он решил сходить в поход продолжительностью L дней.

Программист нашёл интернет-сайт с прогнозом погоды и выяснил для каждого дня отпуска прогнозируемую вероятность дождя ai. Он решил выбрать для похода такие дни, что в день выхода и в день возвращения наверняка будет солнечно (вероятность дождя равна нулю), а сумма вероятностей дождя в промежуточные дни будет минимальной.

Требуется определить оптимальный период для похода или выяснить, что сходить в поход не удастся. Если существует несколько оптимальных вариантов, следует вывести тот, который начинается раньше.

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

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

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

В выходной файл должно быть выведено единственное число — номер первого дня похода, либо −1, если поход невозможен.

Ограничения

1 ≤ L ≤ N ≤ 31, 0 ≤ ai ≤ 100

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
4 2
50 0 0 10
 
2
2 
7 3
0 75 64 30 0 0 100

-1
3 
10 4
0 0 1 2 0 3 4 0 100 0

2
0.029s 0.007s 15