D - 足ゲーム Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

今、タコ星人の間で足ゲームというゲームが流行っています。足ゲームとは、N 個のボタンを T 秒の間の決められたタイミングで踏むとクリアすることが出来るというゲームです。ボタン i は A_i 秒ごとに 1 回踏まなければなりません。つまり、足ゲームをクリアするためには T 秒の間、ボタン i を開始から A_i 秒後、2 \times A_i 秒後、3 \times A_i 秒後・・・のタイミングで 1 回ずつ踏まなければなりません。

タコ星人は変身能力を持っていて、自分の足の本数を自由に変えることが出来ます。タコ星人が同じタイミングで X 個のボタンを踏むためには X 本の足が必要です。足ゲームをクリアするためには何本の足が必要となるでしょう。

入力

入力は以下の形式で標準入力から与えられる。

N T
A_1
A_2
:
A_N
  • 1 行目には、足ゲームのボタンの個数を表す整数 N (1 ≦ N ≦ 1000) と、足ゲームのプレイ時間を表す整数 T (1 ≦ T ≦ 1000) が空白区切りで与えられる。
  • 2 行目からの N 行では、各ボタンを踏むタイミングの情報が与えられる。このうち i 行目には、ボタン i を踏む間隔を表す整数 A_i (1 ≦ A_i ≦ T) が与えられる。

出力

タコ星人が足ゲームをクリアするために必要な足の本数を表す 1 つの整数を 1 行に出力せよ。また、出力の末尾には改行を入れること。

入力例1

2 6
2
3

出力例1

2

この入力例では、

  • ボタン 1 を、開始から 2 秒後と 4 秒後と 6 秒後のタイミング
  • ボタン 2 を、開始から 3 秒後と 6 秒後のタイミング

で踏む必要があります。

開始から 6 秒後のタイミングでは 2 つのボタンを同時に踏む必要があるため、足は 2 本必要です。

入力例2

2 5
2
3

出力例2

1

入力例3

4 40
7
4
3
14

出力例3

3