题目描述

给你 $N$ 个区间，其中第 $i$ 个区间表示为 $[L_i; R_i]$。

现在你要生成 $N$ 个整数，其中第 $i$ 个整数为区间 $[L_i; R_i]$ 范围内的一个随机的整数。

即对于任意 $L_i \le j \le R_i$，第 $i$ 个生成的数字等于 $j$ 的概率为 $\frac{1}{R_i - L_i + 1}$。

你希望 $N$ 个生成的数中至少有 $K\%$ 个数是以 $1$ 开头的数字（即最高位为 $1$），求概率。

输入格式

第一行，一个整数 $N(1 \le N \le 1000)$。

接下来 $N$ 行，每行包含两个整数 $L_i$ 和 $R_i$，以一个空格分隔（$1 \le L_i \le R_i \le 10^{18}$）。

最后一行，一个整数 $K(0 \le K \le 100)$。

输出格式

输出一个浮点数，保留 $6$ 位小数。表示 $N$ 个数中有 $\ge K$ 个数是以 $1$ 开头的数的概率。

样例

1
1 2
50

0.500000

3
1 5
2 10
3 17
2

0.668148