← 返回题目列表

AtCoder · awc0018_d

D. 智能购物者

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥来到一家商店,预算为 K 日元。

商店有 N 展示的商品,以及该商品的价格 i- 第一项是 C_i 日元。高桥可以从这些物品中选择任何自己喜欢的物品进行购买,但每种物品最多只能购买一件。他也可能选择什么都不买。

但是,购买物品的总价不得超过预算 K 日元。

高桥希望在满足此条件的同时最大化所购商品的总价。

在选择商品的所有方式中,总价最多为 K,找到最大可能的总价。

约束

  • 1 \leq N \leq 100
  • 1 \leq K \leq 10^4
  • 1 \leq C_i \leq 10^4 (1 \leq i \leq N)
  • 所有输入均为整数

输入

N K
C_1 C_2 \ldots C_N
  • 第一行包含一个整数 N 表示项目数和一个整数 K 代表预算,以空格分隔。
  • 第二行包含整数 C_1, C_2, \ldots, C_N 代表商品的价格,以空格分隔。

输出

一行打印所有选择商品方式中的最大总价,使得所购买商品的总价最多为 K.


示例输入 1

3 10
3 5 4

示例输出 1

9

示例输入 2

5 20
6 8 3 11 7

示例输出 2

20

示例输入 3

10 100
12 25 8 33 17 45 6 19 30 14

示例输出 3

100