← 返回题目列表

AtCoder · code_thanks_festival_14_qualb_d

D. 足部游戏

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

問題文

章鱼外星人中现在流行一种叫足游戏的游戏。什么是脚下游戏?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