Problem1153--农场主PIPI

1153: 农场主PIPI

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 206  Solved: 110
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI农场主现在要运送一批水蜜桃到CS市,PIPI有n个水蜜桃,这些水蜜桃按照采摘时间有顺序,另外每个水蜜桃有一个含水量,含水量越大价值越高但也容易腐烂。现在为了方便运输,PIPI决定运送采摘时间连续的c个水蜜桃,同时要求运送水蜜桃的含水量之和不超过t,问PIPI有多少种选择方式?

Input

多组样例输入。
对于每一组样例。第一行数据三个整数:n,t,c(1≤n≤105,0≤t≤109,1≤c≤n),第二行按采摘时间给出每个水蜜桃的含水量ai(0≤ai≤109)

Output

对于每一组样例,输出一个整数,代表选择方案数。

Sample Input

3 100 2
1 2 3

Sample Output

2

Source/Category