← 返回题目列表

AtCoder · abc251_b

D. 最多3个(法官版)

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

有 N 称为 Weight 的权重 1,重量 2, \dots,重量 N。 重量 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

如果我们只选择重量 1,它的总质量为 1,所以 1 是一个很好的整数。
如果我们只选择重量 2,它的总质量为 3,所以 3 是一个很好的整数。
如果我们选择权重 1 和 2,它们的总质量为 4,所以 4 是一个很好的整数。
没有其他整数是好的整数。 另外,所有的 1, 3,和 4 是小于或等于的整数 W。 因此,答案是 3.


示例输入 2

2 1
2 3

示例输出 2

0

没有小于或等于的好整数 W.


示例输入 3

4 12
3 3 3 3

示例输出 3

3

有 3 好整数: 3, 6,和 9.
例如,如果我们选择权重 1, 2,和 3,它们的总质量为 9,所以 9 是一个很好的整数。
请注意 12 is 不 一个好的整数。


示例输入 4

7 251
202 20 5 1 4 2 100

示例输出 4

48