<? echo $row['title']." - ".$MSG_PROBLEM." - ".$OJ_NAME; ?>

Problem2308--At Most 3 (Judge ver.)

2308: At Most 3 (Judge ver.)

_{[Creator : ]}

Time Limit : 1.000 sec Memory Limit : 128 MB

Submit Solved: 2 Submit Num: 2 Statistics

Description

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

$\leq N \leq 300$
$\leq W \leq 10^6$
$\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 Copy

2 10
1 3

Sample Output Copy

HINT

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

.

Source/Category

AtCoder

Submit