/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
高橋君はラーメン屋に来ています。
このラーメン屋では N 種類のトッピングがあり、i 番目のトッピングは価格が i、嬉しさが W_i です。
高橋君は、価格の総和が V 以下になるように相異なる 3 種類のトッピングを選びます。 高橋君が選んだトッピングの嬉しさの総和の最大値を求めてください。
ただし、価格の総和が V 以下になるように相異なる 3 種類のトッピングを選ぶ方法が 1 通り以上存在することが制約より保証されます。
制約
- 3 \leq N \leq 100
- 6 \leq V \leq 3N-3
- 1 \leq W_i \leq 10^6
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N V W_1 W_2 \dots W_N
出力
答えを一行で出力せよ。
入力例 1
5 9 31 41 59 26 53
出力例 1
143
1,3,5 番目のトッピングを選んだとき、価格の総和は 1+3+5=9、嬉しさの総和は 31+59+53=143 です。
入力例 2
10 16 102228 448944 131224 326172 500169 670309 976672 579051 974511 773940
出力例 2
2095925
2,6,7 番目のトッピングを選んだとき、価格の総和は 2+6+7=15、嬉しさの総和は 448944+670309+976672=2095925 です。
Score : 200 points
Problem Statement
Takahashi is at a ramen shop.
This shop has N kinds of toppings, and the i-th topping has a price of i and a happiness of W_i.
Takahashi chooses three distinct kinds of toppings so that the total price is at most V. Find the maximum possible total happiness of the toppings he chooses.
The constraints guarantee that there is at least one way to choose three distinct kinds of toppings so that the total price is at most V.
Constraints
- 3 \leq N \leq 100
- 6 \leq V \leq 3N-3
- 1 \leq W_i \leq 10^6
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N V W_1 W_2 \dots W_N
Output
Output the answer in one line.
Sample Input 1
5 9 31 41 59 26 53
Sample Output 1
143
When choosing the first, third, and fifth toppings, the total price is 1+3+5=9, and the total happiness is 31+59+53=143.
Sample Input 2
10 16 102228 448944 131224 326172 500169 670309 976672 579051 974511 773940
Sample Output 2
2095925
When choosing the second, sixth, and seventh toppings, the total price is 2+6+7=15, and the total happiness is 448944+670309+976672=2095925.