I - Buffalo
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
N 個の容器があり、i 番目の容器には A_i リットルの水を入れることができます。
うしくんは N 個の容器の中から 2 個の容器を選んで、以下の操作をそれぞれ任意の回数繰り返し行うことにより、 2 個の容器に合計で K リットルの水が入っている状態にしたいです。
- 操作 1 : 一方の容器を水でいっぱいにする。
- 操作 2 : 容器 X からもう一方の容器 Y に、Y がいっぱいになるか X が空になるまで水をうつす。
- 操作 3 : 一方の容器の中の水を全て捨てる。
上記の方法で K リットルの水を汲み出すことができるような容器のペアの選び方の数を求めてください。
ただし、最初はどの容器も空で、また、選んだ一方の容器を全く使わなくても構いません。
制約
- 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 リットルの水を汲み出すことができます。
- 2 番目の容器を水でいっぱいにする。
- 2 番目の容器から 1 番目の容器に、1 番目の容器がいっぱいになるまで水をうつす。
- 1 番目の容器の中の水を全て捨てる。
入力例 2
3 11 5 6 11
出力例 2
3
どのペアを選んでも 11 リットルの水を汲み出すことができます。
入力例 3
3 10 3 4 5
出力例 3
0