#387. C - 搬运行李

C - 搬运行李

C - 搬运行李

题目描述

高桥有 NN 件物品,编号为 11 到 NN,以及一辆载重上限为 CC 的推车。第 ii 件物品的重量为 WiW_i。

对于每件物品,高桥可以选择:

  • 放在推车上;
  • 用手拿着;
  • 不携带。

他会一次性携带选中的全部物品,并且必须满足:

  • 推车上所有物品的总重量不超过 CC;
  • 用手拿的物品至多一件,且对这件物品的重量没有限制。

求高桥一次最多能够携带多少件物品。

输入格式

第一行输入两个整数 N,CN,C。

第二行输入 NN 个整数 W1,W2,…,WNW_1,W_2,\ldots,W_N。

输出格式

输出一次最多可以携带的物品数量。

数据范围

  • 1≤N≤2×1051\le N\le2\times10^5
  • 1≤C≤10141\le C\le10^{14}
  • 1≤Wi≤1091\le W_i\le10^9
  • 所有输入均为整数。

样例输入 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