题目描述

高桥君来到了一家拉面店。

这家拉面店有 $N$ 种配料，第 $i$ 种配料的价格为 $i$，幸福度为 $W_i$。

高桥君要选择 $3$ 种不同的配料，使得价格总和不超过 $V$。请求出他所选配料的幸福度总和的最大值。

根据约束条件，保证至少存在一种选择 $3$ 种不同配料使得价格总和不超过 $V$ 的方法。

输入格式

输入按以下格式从标准输入读入：

• $N$ $V$
• $W_1$ $W_2$ $\ldots$ $W_N$

输出格式

输出一行答案。

5 9
31 41 59 26 53

143

选择第 $1, 3, 5$ 种配料时，价格总和为 $1+3+5=9$，幸福度总和为 $31+59+53=143$。

10 16
102228 448944 131224 326172 500169 670309 976672 579051 974511 773940

2095925

选择第 $2, 6, 7$ 种配料时，价格总和为 $2+6+7=15$，幸福度总和为 $448944+670309+976672=2095925$。

数据范围

• $3 \leq N \leq 100$

• $6 \leq V \leq 3N-3$

• $1 \leq W_i \leq 10^6$

• 所有输入值均为整数。

• 来源：AtCoder ABC 478 B

子任务设置

• 子任务 1（100 分）：无特殊限制。