← 返回题目列表

Codeforces · 498/B

B. 命名那首曲子

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

原来你是摇滚乐队 AC/PE 的忠实粉丝。彼得得知这一点,开始了下面的游戏:他播放该组的 n 首歌曲列表中的第一首歌,你必须找出这首歌的名称。当你说出歌曲名称后,Peter 立即按顺序播放下面的歌曲,依此类推。

AC/PE的第i首歌曲有其可识别性pi。这意味着,如果您尚未识别出这首歌曲,那么您再听一秒钟,您就有 pi% 的概率识别出它并说出它的名称。否则你就继续听。请注意,只有当歌曲开始播放后的整数秒数时,您才能尝试猜测它。

在所有 AC/PE 歌曲中,副歌的第一个单词与标题相同,因此当您听到第 i 首歌曲的前 ti 秒并且副歌开始时,您会立即猜到它的名字。

比如《红色公路》这首歌,副歌部分听起来很晚,但辨识度很高。另一方面,在歌曲《Back In Blue》中,标题中的单词听起来很接近歌曲的开头,但在听到这些单词之前很难说出它的名字。您可以在最初几秒钟内说出这两首歌曲的名称。

确定如果游戏持续恰好 T 秒,您将识别的预期歌曲数(即您可以在游戏停止后的第二个 T 上进行最后的猜测)。

如果所有歌曲的识别速度都快于 T 秒,则游戏会在识别完最后一首歌曲后停止。

输入

输入的第一行包含数字 n 和 T (1 ≤ n ≤ 5000, 1 ≤ T ≤ 5000),以空格分隔。接下来的 n 行包含数字 pi 和 ti 对(0 ≤ pi ≤ 100, 1 ≤ ti ≤ T)。这些歌曲的排列顺序与 Petya 列表中的顺序相同。

输出

输出一个数字——T秒内你将识别的歌曲数量的预期数字。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。

示例

输入 #1

2 2
50 2
10 1

输出 #1

1.500000000

输入 #2

2 2
0 2
100 2

输出 #2

1.000000000

输入 #3

3 3
50 3
50 2
25 2

输出 #3

1.687500000

输入#4

2 2
0 2
0 2

输出#4

1.000000000