Задача F. То березка, то рябина...

Автор:Жюри ROI-2007   Ограничение времени:1 сек
Входной файл:trees.in   Ограничение памяти:256 Мб
Выходной файл:trees.out  
Максимальный балл:100  

Условие

В целях улучшения ландшафтной архитектуры и экологической обстановки управление городского хозяйства разработало проект программы озеленения центрального проспекта. Согласно проекту с одной стороны проспекта планируется высадить в ряд деревья K различных видов, для чего были закуплены саженцы деревьев, причем i-го вида было закуплено ai саженцев.

Для достижения эстетического совершенства высаживаемого ряда деревьев требуется, чтобы среди любых P подряд идущих деревьев все деревья были разных видов. Если количество деревьев в ряду меньше P, то все они должны быть различны.

Требуется написать программу, которая находит максимальное количество деревьев в эстетически совершенном ряду, посаженном из закупленных саженцев.

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

Первая строка входного файла содержит два целых числа: K — количество различных видов деревьев (1 ≤ K ≤ 105), и P — требуемое количество подряд идущих деревьев разных видов (2 ≤ P ≤ K). Последующие K строк входного файла содержат целые числа ai — количество закупленных саженцев деревьев i-го вида ($1 \le a_i \le 10^9), по одному числу в каждой строке.

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

Выходной файл должен содержать единственное число — максимальное количество деревьев, посадка которых в ряд в некотором порядке достигает эстетического совершенства.

В приведенном примере деревья можно высадить, например, в следующем порядке: 2, 4, 3, 1, 2, 3, 1, 2.

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

Входной файл (trees.in) Выходной файл (trees.out)
1
4 3
2
5
2
1
8

0.033s 0.007s 15