15708번 - 미네크래프트

문제

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

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

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

입력

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

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

출력

문제의 정답을 출력하라.

제한

힌트