分数: 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