星星之火,可以燎原

题目来源

原创

题目描述

在一片荒芜的原野上,一团星火越燃越猛,彷如一把利刃,划破了静寂的天空。

n 团火焰,每团火焰都有一个大小 w_i ,整片草原的面积为 m ,每次你可以任选一团火焰灼烧草原,使草原的面积变为 m-w_i ,但是有一条规定,不可以连续选择 x 团大小大于 t 的火焰,现在问你,最少需要多少团火焰才能烧完整个草原(即草原大小 <=0 )。

输入格式

第一行四个正整数 n,m,t,x
第二行 n 个正整数 w_i

输出格式

烧完草原所需要的最少次数

样例

Input 1

2 3 4 4
2 7

Output 1

1

提示说明

保证不存在连最优结果都烧不完草原的情况。
1<=x<=n<=100
1<=m,t,w_i<=1000

2 个赞