합주 연습

시간 제한1초메모리 제한1024 MB

요약

정해진 순서로 반복되는 n개의 공연 길이가 주어질 때, 하루에 p만큼 공연할 수 있는 k일 동안 완전한 공연 순회가 몇 번 가능한지 구한다.

난이도: 보통10점 중 6점
유형: 이분 탐색, 누적 합, 시뮬레이션, 수학
정답자: 아직 제출이 없습니다

문제

음악을 전공하는 n명의 학생이 연주회를 준비하기 위해 연주홀에서 합주 연습을 한다. 연습 한 회차에서는 학생 1부터 학생 n까지 순서대로 각자 한 번씩 연주한다. 학생 i의 연주 시간은 di이다. 마지막 학생의 연주가 끝나면 곧바로 학생 1의 연주부터 다음 연습 회차가 시작된다.

연주홀은 매일 정해진 p만큼의 시간 동안 문을 연다. 어느 순간 다음 학생의 연주가 연주홀이 닫히기 전에 끝날 수 없다면, 현재 연습 회차에 남은 연주는 모두 다음 날로 넘어간다.

k일 동안 학생들은 온전한 연습 회차를 몇 번 완료할 수 있는가?

입력

첫째 줄에 세 정수 n, p, k가 주어진다. (1 ≤ n ≤ 2 · 105, 1 ≤ p, k ≤ 109) 다음 n개의 줄에 각각 하나의 정수가 주어진다. i번째 줄에는 di가 주어진다. (1 ≤ di ≤ p)

출력

k일 동안 학생들이 완료할 수 있는 온전한 연습 회차의 수를 출력한다.

예제3

예제 1
입력
```
3 9 5
1
2
3
```
예상 출력
```
7
```
예제 2
입력
```
4 10 5
3
2
4
6
```
예상 출력
```
2
```
예제 3
입력
```
3 10 2
5
6
7
```
예상 출력
```
0
```