配点 : $200$ 点

問題文

おもり $1$, おもり $2$, $\dots$, おもり $N$ の $N$ 個のおもりがあります。おもり $i$ の重さは $A_i$ です。 以下の条件を満たす正整数 $n$ を 良い整数 と呼びます。

• $\bf{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$

出力

答えを出力せよ。

2 10
1 3

3

おもり $1$ のみを選ぶと重さの和は $1$ になります。よって $1$ は良い整数です。 おもり $2$ のみを選ぶと重さの和は $3$ になります。よって $3$ は良い整数です。 おもり $1$ とおもり $2$ を選ぶと重さの和は $4$ になります。よって $4$ は良い整数です。 これら以外に良い整数は存在しません。また、$1,3,4$ のいずれも $W$ 以下の整数です。よって答えは $3$ 個になります。

2 1
2 3

0

$W$ 以下の良い整数は存在しません。

4 12
3 3 3 3

3

良い整数は $3,6,9$ の $3$ 個です。 たとえばおもり $1$, おもり $2$, おもり $3$ を選ぶと重さの和は $9$ になるので、$9$ は良い整数です。 $12$ は良い整数 ではない ことに注意してください。

7 251
202 20 5 1 4 2 100

48