시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 29 17 16 57.143%

문제

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

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

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

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1

3 3
1 2 3

예제 출력 1

1

예제 입력 2

5 4
2 1 4 3 5

예제 출력 2

4