在概率论中,已知以下悖论,称为本福德定律:“在许多取自真实来源的随机数列表中,以数字 1 开头的数字比以任何其他数字开头的数字出现的频率要高得多”(这是该定律的最简单形式)。
在 Codeforces 上读到相关内容后,Hedgehog 对该声明很感兴趣,并希望彻底探索它。他发现以下类似的问题特别有趣:有 N 个随机变量,其中第 i 个可以从某个段 [Li;Ri] 中取任何整数值(该段中的所有数字都是等概率的)。这意味着第 i 个数量的值可以等于给定区间 [Li;Ri] 中的任何整数,概率为 1 / (Ri - Li + 1)。
刺猬想知道这些值中至少 K% 的第一位数字等于 1 的事件的概率。换句话说,让我们考虑这些随机变量的一些固定值,并只保留每个值的第一位数字(MSD - 最高有效数字)。然后让我们计算一下遇到数字 1 的次数,如果在这 N 个值中至少有 K% 遇到该数字,则这样的一组值将被称为好的值。您必须找到给定随机变量的一组值是好的值的概率。
输入
第一行包含数字 N,它是随机变量的数量 (1 ≤ N ≤ 1000)。然后跟随包含数字对 Li、Ri 的 N 行,每个数字都是一个随机变量的描述。保证1≤Li≤Ri≤1018。
最后一行包含一个整数 K (0 ≤ K ≤ 100)。
输入文件中的所有数字都是整数。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin (也可以使用 %I64d)。
输出
打印所需的概率。以一定精度打印小数,使结果的相对误差或绝对误差不超过 10 - 9。
示例
输入 #1
1 1 2 50
输出 #1
0.500000000000000
输入 #2
2 1 2 9 11 50
输出 #2
0.833333333333333