Правила новой телевизионной викторины следующие. В ряд расположены \(n\) ячеек, пронумерованных от \(1\) до \(n\), в \(i\)-й ячейке находится \(a_i\) монет.
Игрок может выбрать целое число \(b\) и заплатить \(b\) монет. Тогда ведущий забирает монеты из всех ячеек, где лежит не более \(b\) монет, соответствующие ячейки становятся пустыми. После этого среди любых \(k\) подряд идущих ячеек должно быть не менее \(m\) пустых. После этого игрок забирает все оставшиеся на поле монеты, если он забрал \(a\) монет, его выигрыш составит \(a-b\) монет.
Помогите игроку понять, какое максимальный выигрыш он может гарантировать.
Формат входных данных
На первой строке ввода находятся целые числа \(n\), \(k\) и \(m\) (\(1 \le m < k \le n \le 200\,000\)).
На второй строке находятся \(n\) целых чисел \(a_i\) (\(1 \le a_i \le 10^9\)).
Формат выходных данных
Выведите одно число: какой максимальной выигрыш может гарантировать себе игрок.
Примечание
В первом примере игрок выбирет \(b = 5\). После удаления монет из ячеек, в которых лежит не более чем по \(5\) монет, количество монет в ячейках оказывается равно \([0, 7, 0, 0, 0, 9, 0, 6]\), суммарно он забирает из ячеек \(22\) монеты, с учетом ранее отданных \(5\) монет выигрыш игрока составляет \(17\) монет.
Во втором примере, чтобы добиться, чтобы среди любых двух подряд идущих ячеек была хотя бы одна пустая, игроку приходится выбрать \(b = 2\). После этого монет в ячейках нет, и выигрыш игрока оказывается отрицательным: \(-2\).