二、 武器(weapon)
妖怪看到丁丁的数学非常好,于是厚着脸皮找丁丁帮忙。他拿出了n件武器(编号依次为1~n)和m只相同的盒子,每件武器的重量分别为w[i],每只盒子最大承重为t。丁丁要做的是在妖怪的要求范围内,把尽可能多的武器放进盒子里。
妖怪的要求是:
1. 一件武器不能拆开放在两个或更多的盒子里;
2. 武器必须编号顺序放进盒子里,也就是说如果丁丁把第i件武器放进某个盒子后,他就不能再把编号小于i的武器放进任何盒子。
输入文件(weapon.in)
第一行,三个整数:n,t,m
第二行,n个整数,按编号给出每件武器的重量w[i]
输出文件(weapon.out)
一个整数,表示最多可以装进m只盒子里的武器数量。
样例输入:
4 5 2
4 3 4 2
样例输出:
3
数据范围:
50%的数据 0<=n,t,m,w[i]<=20
100%的数据 0<=n,t,m,w[i]<=200