23036번 - CAN WIN

문제

가톨릭대를 다니는 아리와 쿠기는 다솔관에서 공부를 하던 와중에 시원한 커피가 마시고 싶어졌다.

하지만 너무 더운 날씨 때문에 둘은 서로 나가기 싫어 눈치만 보기 시작했다.

커피를 포기할 수 없던 둘은 결국 책 펼치기 게임을 통해 진 사람이 커피를 사오기로 결정했다.

책 펼치기 게임의 규칙은 다음과 같다.

1. 한명이 임의의 책을 고른다. (아리와 쿠기는 서로 다른 책을 고른다.)
2. 고른 책에서 본인이 지정할 범위의 시작 쪽과 끝 쪽을 정한다.
3. 시작 쪽에서 끝 쪽의 범위 안에 포함된 영어 단어의 개수를 세어준다.
4. 세어준 영어 단어의 개수를 지정한 범위의 페이지 수로 나눈 것을 점수로 한다.

아리가 먼저 진행을 하여 P 점을 얻었고 쿠기는 자기 차례가 되자 아리에게 지지 않을 경우의 수가 궁금해졌다.

쿠기를 도와 쿠기가 아리에게 지지 않을 경우의 수가 몇 개인지 구해보자.

입력

첫째 줄에 쿠기가 고른 책의 총 페이지 수인 N (1 ≤ N ≤ 1,000,000 인 정수) 와

아리가 얻은 점수 P (0 ≤ P ≤ 1,000,000,000 인 정수) 가 주어진다.

다음 줄에 쿠기가 고른 책의 각 페이지당 영어단어의 개수 W (0 ≤ W ≤ 1,000,000,000 인 정수) 가 N 쪽만큼 차례로 주어진다.

출력

쿠기의 점수가 P (아리의 점수) 보다 크거나 같을 경우의 수를 구하시오.

제한

힌트