Zane and Zane's crush have just decided to date! However, the girl is having a problem with her Physics final exam, and needs your help.
There are
n questions, numbered from
1 to
n. Question
i comes before question
i+1 (
1≤i<n). Each of the questions cannot be guessed on, due to the huge penalty for wrong answers. The girl luckily sits in the middle of two geniuses, so she is going to cheat.
However, the geniuses have limitations. Each of them may or may not know the answers to some questions. Anyway, it is safe to assume that the answers on their answer sheets are absolutely correct.
To make sure she will not get caught by the proctor, the girl will glance
at most p times, each time looking at
no more than k consecutive questions on one of the two geniuses' answer sheet. When the girl looks at some question on an answer sheet, she copies the answer to that question if it is on that answer sheet, or does nothing otherwise.
Help the girl find the maximum number of questions she can get correct.
Output
Print one integer− the maximum number of questions the girl can answer correctly.
Note
Let
(x,l,r) denote the action of looking at all questions
i such that
l≤i≤r on the answer sheet of the
x-th genius.
In the first sample, the girl could get
4 questions correct by performing sequence of actions
(1,1,3) and
(2,5,6).
In the second sample, the girl could perform sequence of actions
(1,3,5),
(2,2,4), and
(2,6,8) to get
7 questions correct.