/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は予算 K 円を持ってお店にやってきました。
お店には N 個の商品が並んでおり、 i 番目の商品の価格は C_i 円です。高橋君はこれらの商品の中から好きな商品を選んで購入できますが、各商品は最大1つまでしか購入できません。また、何も購入しなくても構いません。
ただし、購入する商品の価格の合計は予算 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
- 1 行目には、商品の個数を表す整数 N と、予算を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各商品の価格を表す整数 C_1, C_2, \ldots, C_N が、スペース区切りで与えられる。
出力
購入する商品の価格の合計が K 以下となるような選び方における、価格の合計の最大値を 1 行で出力せよ。
入力例 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
Score : 366 pts
Problem Statement
Takahashi has come to a store with a budget of K yen.
The store has N items on display, and the price of the i-th item is C_i yen. Takahashi can choose any items he likes from these items to purchase, but he can buy at most one of each item. He may also choose to buy nothing at all.
However, the total price of the purchased items must not exceed the budget of K yen.
Takahashi wants to maximize the total price of the purchased items while satisfying this condition.
Among all ways to select items such that the total price is at most K, find the maximum possible total price.
Constraints
- 1 \leq N \leq 100
- 1 \leq K \leq 10^4
- 1 \leq C_i \leq 10^4 (1 \leq i \leq N)
- All inputs are integers
Input
N K C_1 C_2 \ldots C_N
- The first line contains an integer N representing the number of items and an integer K representing the budget, separated by a space.
- The second line contains integers C_1, C_2, \ldots, C_N representing the prices of the items, separated by spaces.
Output
Print in one line the maximum total price among all ways to select items such that the total price of the purchased items is at most K.
Sample Input 1
3 10 3 5 4
Sample Output 1
9
Sample Input 2
5 20 6 8 3 11 7
Sample Output 2
20
Sample Input 3
10 100 12 25 8 33 17 45 6 19 30 14
Sample Output 3
100