Профессор Селезнев передает Алисе зашифрованную информацию, которая представляет собой последовательность целых чисел. Все числа данной последовательности не превышают 10
7. Каждое число передается в течении одной секунды. Чтобы понять, что данные переданы правильно, Алисе необходимо определить контрольное значение, которое вычисляется по следующему правилу:
- берутся три переданных значения из последовательности таким образом, чтобы между между какими-либо двумя соседними моментами передачи прошло ровно
K секунд (между передачей первого выбранного числа и второго или между передачей второго выбранного числа и третьего);
- вычисляется сумма выбранных чисел, которая должна быть максимальной. Данная сумма является контрольным значением.
Помогите Алисе определить контрольное значение.
Формат входных данных
В первой строке записано количество чисел
N (
1 ≤ N ≤ 2·105) и целое число
K (
1 ≤ K < 105, K < N). Каждая из следующих
N строк содержит одно целое число, по модулю не превышающее
107.
Формат выходных данных
Выведите одно число - контрольное значение.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3
1
5
6
7
8
2
|
16
|