시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 324 86 66 31.579%

문제

미네크래프트에 있는 디디는 집을 짓기 위해 돌을 채취하려고 한다. N개의 바위들이 일렬로 놓여져 있고, 디디는 현재 첫 번째 바위에 위치해 있다. 각 바위 i는 서로 같거나 다른 강도를 가지고 있어서, 바위에서 돌을 채취하기 위해 해야 하는 곡괭이질의 수 Ki 또한 서로 같거나 다르다. 디디는 돌을 채취하기 위해 다음과 같은 행동을 할 수 있다.

  1. 시간 1을 소비하여, 디디가 위치해 있는 바위에 곡괭이질을 1번 한다.
  2. 시간 P를 소비하여, 이웃한 바위로 이동한다.

디디에게 T만큼의 시간이 주어졌을 때, 채취할 수 있는 돌의 최대 개수를 출력하는 프로그램을 작성하라.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 105), T(1 ≤ T ≤ 109), P(1 ≤ P ≤ 105)가 공백으로 구분되어 주어진다.

둘째 줄에 바위 i(i = 1, 2, ..., N)를 채취하기 위해 필요한 곡괭이질의 수 Ki(1 ≤ Ki ≤ 105)가 공백으로 구분되어 주어진다.

출력

문제의 정답을 출력하라.

예제 입력 1

6 17 1
3 5 2 6 9 1

예제 출력 1

4

출처

Contest > 네블컵 > 제 1회 네블컵 B번