33678번 - 로마의 휴일

문제

직장인 로마는 휴가에 맞춰 좋아하는 아이돌의 콘서트에 가고 싶어 한다. 하지만 콘서트 티켓을 구매할 돈이 없어 일을 하며 돈을 모으려고 한다. 동시에 가능한 한 오랫동안 휴가를 다녀오고 싶어 한다.

• 로마는 $N$일 중 한 번만 연속된 기간을 선택하여 휴가를 사용할 수 있다.
• 휴가를 다녀온 후에는 $i$일에 일을 하면 $a_{i}$만큼 일급을 받는다.
• 휴가를 다녀오기 전에는 $i$일에 일을 하면 보너스가 적용되어 $a_{i} \times X$만큼 일급을 받는다.
• 휴가 중에는 일을 하여 일급을 받을 수 없으며, 첫날부터 휴가를 다녀올 수 있다.

콘서트 티켓 비용은 후불로 지불할 수 있기 때문에 휴가를 가기 전에 번 돈과 휴가를 갔다 와서 번 돈의 합이 $K$ 이상이면 된다. 만약 어떠한 방법으로도 티켓을 구매할 수 없다면 휴가를 나가지 않는다.

주어진 일 수 $N,ドル 콘서트 티켓 비용 $K,ドル 일급 보너스 $X,ドル 일급 $a_1, a_2, \cdots, a_N$이 주어질 때 최대 며칠 동안 휴가를 다녀올 수 있는지 프로그램을 작성하자.

입력

첫 번째 줄에 정수 $N,ドル $K,ドル $X$가 공백으로 구분되어 주어진다.

두 번째 줄에는 정수 $a_1, a_2, \cdots , a_N$이 공백으로 구분되어 주어진다.

출력

최대 며칠까지 휴가를 다녀올 수 있는 지 출력한다. 만약 휴가를 다녀오지 못한다면 -1을 대신 출력한다.

제한

• 2ドル \leq N \leq 200,000円$
• 1ドル \leq K \leq 10^{9}$
• 1ドル \leq X \leq 10$
• 1ドル \leq a_i \leq 1,000円$

노트