Зейн и его возлюбленная назначили свидание! Однако, у девушки проблемы с экзаменом по физике, и ей нужна ваша помощь.
В экзамене n вопросов, пронумерованных от 1 до n. Вопрос i идет перед вопросом i + 1 (1 ≤ i < n). Каждый из вопросов не может быть угадан. К счастью, девушка сидит как раз мжду двумя гениями, и она решила списать.
Однако, даже гении знают ответы не на все вопросы: про каждый вопрос они либо знают ответ, либо нет. Однако, если они знают ответ, то он верный.
Чтобы не быть уличенной в списывании, девушка может бросить взгляд на ответы соседа не более p раз, каждый раз смотря на не более чем k последовательных вопросов на листе ответов одного из двух гениев. Когда девушка смотрит на ответ на какой-то из вопросов, она списывает ответ, если он есть, и ничего не делает иначе.
Помогите девушке узнать максимальное число вопросов, на которые она может ответить.
Выходные данные
Выведите одно целое число — максимальное число вопросов, на которые девушка может узнать ответ.
Примечание
Пусть (x, l, r) означает подглядывание ответа на все вопросы i такие, что l ≤ i ≤ r на листе ответов x-го гения.
В первом примере девушка может узнать ответы на 4 вопроса, выполнив действия (1, 1, 3) и (2, 5, 6).
Во втором примере девушка может выполнить операции (1, 3, 5), (2, 2, 4) и (2, 6, 8), чтобы узнать ответ на 7 вопросов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 2 3
3 1 3 6
4 1 2 5 6
|
4
|
|
2
|
8 3 3
4 1 3 5 6
5 2 4 6 7 8
|
7
|