30209번 - 참호전

문제

적군의 참호 $N$개가 일렬로 늘어서 있다. 국군의 지휘관은 각 참호에 대응하기 위해 적군의 참호를 늘어선 순서대로 1,ドル 2, \cdots, N$번의 번호를 붙였고, $i$번 참호에는 적군이 $a_i$명 배치되어 있다는 사실을 알아냈다.

지휘관은 참호전을 위해 각 적군 참호에 대응하는 아군 참호를 맞은편에 1ドル$개씩 모두 설치했고, 휘하에 있는 $M$명의 국군을 각각의 아군 참호에 나누어 배치하려 한다. 각 아군 참호에는 0ドル$명 이상의 국군을 배치할 수 있고, 아군 참호별로 맞은편의 적군 참호에게서 승리하기 위해서는 맞은편의 적군 참호에 있는 적군 수보다 많은 국군을 아군 참호에 배치해야 한다.

지휘관은 폭격기로 폭탄을 하나 투하해 특정한 범위 내 연속한 번호의 적군 참호를 모두 폭파할 수 있다. 이때 지휘관은 폭격기의 폭탄 투하 위치와 폭탄의 폭파 범위를 설정할 수 있으며, 적군 참호를 폭파하면 해당 적군 참호에게서 승리한 것으로 간주한다. 하지만 동맹국에서 폭탄에 의한 인명피해를 최소화해달라는 요청이 있었다. 따라서 폭격기로 폭탄을 투하하지 않거나, 투하한다면 폭파한 적군 참호에 배치된 적군 수의 합이 $K$명 이하여야 한다.

지휘관은 폭격기의 폭탄 투하 위치와 폭탄의 폭파 범위를 설정하고 각 아군 참호에 배치할 국군의 수를 적절히 나누어 최대한 많은 적군 참호에게서 승리하도록 전략을 세우려 한다. 지휘관이 승리할 수 있는 적군 참호의 최대 개수를 구하여라.

입력

첫 번째 줄에 적군 참호의 수 $N,ドル 국군의 수 $M,ドル 폭탄의 인명피해 제한 $K$가 공백으로 구분되어 정수로 주어진다. $(1 \leq N \leq 200,000円;$ 1ドル \leq M \leq 10^{18};$ 1ドル \leq K \leq 10^{18})$

두 번째 줄에 각 적군 참호에 배치된 적군의 수 $a_1, a_2, \cdots, a_N$이 공백으로 구분되어 정수로 주어진다. $(1 \leq a_i \leq 10^{9})$

출력

첫 번째 줄에 지휘관이 승리할 수 있는 적군 참호의 최대 개수를 출력한다.

제한

힌트