Get Max Programs

You may only delete some programs from the beginning, keeping a suffix. The suffix runs in its original order, and no program can be interrupted. Each time slot has length k; a program that fits must run in the current slot, otherwise it moves to the next slot. With at most m slots, find the maximum length of an executable suffix.

输入格式

The first line contains n m k; the second line contains the program durations. 1≤n,m≤200000; 1≤k≤10^9; the full original constraint is 1≤time[i]≤k.

输出格式

Output a single integer, the answer.

样例 1

输入：

5 2 6
5 2 1 4 2

输出：

4

样例 2

输入：

5 1 4
4 2 3 4 1

输出：

1

样例 3

输入：

5 3 3
1 2 3 1 1

输出：

5

样例说明

The answers are 4, 1 and 5. In the second example you cannot pick a longer range in the middle; the last program must be included.