← 返回题目列表

AtCoder · qupc2018_i

I. 布法罗

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

配点 : 800 点

問題文

N 有...个容器,i 第...个容器中有 A_i 可以装入rittorun的水。

小牛君 N 从 个容器中选择 个容器 2 通过分别任意次数重复进行以下操作, 2 在每个容器中合计 K 想要使其处于装有 rittorun 水的状态。

  • 操作 1 :将两个容器都装满水。
  • 操作 2 : 容器 X 从一个容器向另一个容器 Y 属于Y 直到一个容器装满 X 或另一个容器变空为止,不断倒水。
  • 操作 3 :倒掉一个容器中的全部水。

使用上述方法 K 求能够按照上述方法倒出 rittorun 水的容器对的选择数量。

但是,开始时所有容器都是空的,并且可以完全不使用所选择的某一个容器。

制約

  • 2 \leq N \leq 3 \times 10^5
  • 1 \leq K \leq 2 \times 10^6
  • 1 \leq A_i \leq 10^6
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N K
A_1 A_2 ... A_N

出力

1 行输出答案。


入力例 1

2 3
4 7

出力例 1

1

1 第 个容器和 2 第 个容器,通过进行如下操作 3 可以倒出 rittorun 水。

  • 2 将第 个容器装满水。
  • 2 从第 个容器 1 向第 个容器中倒水,直到1 第 个容器装满为止。
  • 1 倒掉第 个容器中的全部水。

入力例 2

3 11
5 6 11

出力例 2

3

无论选择哪一对 11 可以倒出 rittorun 水。


入力例 3

3 10
3 4 5

出力例 3

0