C - 搬运行李
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
C - 搬运行李
题目描述
高桥有 件物品,编号为 到 ,以及一辆载重上限为 的推车。第 件物品的重量为 。
对于每件物品,高桥可以选择:
- 放在推车上;
- 用手拿着;
- 不携带。
他会一次性携带选中的全部物品,并且必须满足:
- 推车上所有物品的总重量不超过 ;
- 用手拿的物品至多一件,且对这件物品的重量没有限制。
求高桥一次最多能够携带多少件物品。
输入格式
第一行输入两个整数 。
第二行输入 个整数 。
输出格式
输出一次最多可以携带的物品数量。
数据范围
- 所有输入均为整数。
样例输入 1
5 10
3 4 8 2 5
样例输出 1
4
样例输入 2
3 5
10 20 30
样例输出 2
1
样例输入 3
6 15
3 5 2 4 1 10
样例输出 3
6
样例输入 4
15 5000000000
900000000 400000000 600000000 1000000000 300000000 700000000 200000000 800000000 500000000 100000000 850000000 750000000 650000000 950000000 550000000
样例输出 4
11
样例输入 5
1 1
1000000000
样例输出 5
1