102511: [AtCoder]ABC251 B - At Most 3 (Judge ver.)

Problem Statement

There are $N$ weights called Weight $1$, Weight $2$, $\dots$, Weight $N$. Weight $i$ has a mass of $A_i$.
Let us say a positive integer $n$ is a good integer if the following condition is satisfied:

• We can choose at most $3$ different weights so that they have a total mass of $n$.

How many positive integers less than or equal to $W$ are good integers?

Constraints

• $1 \leq N \leq 300$
• $1 \leq W \leq 10^6$
• $1 \leq A_i \leq 10^6$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $W$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the answer.

Sample Input 1

2 10
1 3

Sample Output 1

3

If we choose only Weight $1$, it has a total mass of $1$, so $1$ is a good integer.
If we choose only Weight $2$, it has a total mass of $3$, so $3$ is a good integer.
If we choose Weights $1$ and $2$, they have a total mass of $4$, so $4$ is a good integer.
No other integer is a good integer. Also, all of $1$, $3$, and $4$ are integers less than or equal to $W$. Therefore, the answer is $3$.

Sample Input 2

2 1
2 3

Sample Output 2

0

There are no good integers less than or equal to $W$.

Sample Input 3

4 12
3 3 3 3

Sample Output 3

3

There are $3$ good integers: $3, 6$, and $9$.
For example, if we choose Weights $1$, $2$, and $3$, they have a total mass of $9$, so $9$ is a good integer.
Note that $12$ is not a good integer.

Sample Input 4

7 251
202 20 5 1 4 2 100

Sample Output 4

48

问题描述

有$N$个重量，分别叫做 Weight $1$, Weight $2$, $\dots$, Weight $N$。Weight $i$的重量是$A_i$。

让我们定义一个正整数$n$是好整数，如果满足以下条件：

• 我们可以选择最多3个不同的重量，使它们的总重量为$n$。

有多少个小于等于$W$的正整数是好整数？

限制条件

• $1 \leq N \leq 300$
• $1 \leq W \leq 10^6$
• $1 \leq A_i \leq 10^6$
• 输入中的所有值都是整数。

输入

输入从标准输入按以下格式给出：

$N$ $W$
$A_1$ $A_2$ $\dots$ $A_N$

输出

打印答案。

样例输入1

2 10
1 3

样例输出1

3

如果我们只选择Weight $1$，它的总重量是$1$，所以$1$是好整数。

如果我们只选择Weight $2$，它的总重量是$3$，所以$3$是好整数。

如果我们选择Weight $1$和$2$，它们的总重量是$4$，所以$4$是好整数。

没有其他整数是好整数。另外，所有小于等于$W$的$1$、$3$和$4$都是好整数。因此，答案是$3$。

样例输入2

2 1
2 3

样例输出2

0

没有小于等于$W$的好整数。

样例输入3

4 12
3 3 3 3

样例输出3

3

有$3$个好整数：$3, 6$, 和 $9$。

例如，如果我们选择Weight $1$、$2$和$3$，它们的总重量是$9$，所以$9$是好整数。

注意$12$不是好整数。

样例输入4

7 251
202 20 5 1 4 2 100

样例输出4

48