CF54C.First Digit Law

In the probability theory the following paradox called Benford's law is known: "In many lists of random numbers taken from real sources, numbers starting with digit 1 occur much more often than numbers starting with any other digit" (that's the simplest form of the law).

Having read about it on Codeforces, the Hedgehog got intrigued by the statement and wishes to thoroughly explore it. He finds the following similar problem interesting in particular: there are N random variables, the i-th of which can take any integer value from some segment [L__i;R__i] (all numbers from this segment are equiprobable). It means that the value of the i-th quantity can be equal to any integer number from a given interval [L__i;R__i] with probability 1 / (R__i - L__i + 1).

The Hedgehog wants to know the probability of the event that the first digits of at least K% of those values will be equal to one. In other words, let us consider some set of fixed values of these random variables and leave only the first digit (the MSD — most significant digit) of each value. Then let's count how many times the digit 1 is encountered and if it is encountered in at least K per cent of those N values, than such set of values will be called a good one. You have to find the probability that a set of values of the given random variables will be a good one.

在概率论中，存在一个被称为本福特定律（Benford's law）的著名悖论：“在许多源自真实世界的随机数列表中，以数字 1 开头的数出现的频率远高于以其他任意数字开头的数”（这是该定律最简单的形式）。

刺猬在 Codeforces 上读到这一现象后，对这一陈述产生了浓厚兴趣，并希望深入探究。他尤其对如下类似问题感到有趣：现有 $N$ 个随机变量，其中第 $i$ 个随机变量可在区间 $[L_i; R_i]$ 内取任意整数值（该区间内所有整数等概率出现）。换言之，第 $i$ 个变量取区间 $[L_i; R_i]$ 中任一整数值的概率均为 $1/(R_i - L_i + 1)$。

刺猬希望计算如下事件发生的概率：这些值中，至少有 $K\%$ 的数的首位数字（即最高有效位，MSD）等于 1。换句话说，考虑这些随机变量的一组固定取值，并仅保留每个值的首位数字（MSD），然后统计数字 1 出现的次数；若该次数不少于这 $N$ 个值的 $K\%$，则称这组取值为“好”的。你需要计算：给定的这些随机变量的取值集合为“好”的概率。

The first line contains number N which is the number of random variables (1 ≤ N ≤ 1000). Then follow N lines containing pairs of numbers L__i, R__i, each of whom is a description of a random variable. It is guaranteed that 1 ≤ L__i ≤ R__i ≤ 1018.

The last line contains an integer K (0 ≤ K ≤ 100).

All the numbers in the input file are integers.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).

第一行包含一个整数 $N$，表示随机变量的个数（$1 \leq N \leq 1000$）。随后是 $N$ 行，每行包含一对整数 $L_i,\,R_i$，分别描述一个随机变量。保证 $1 \leq L_i \leq R_i \leq 10^{18}$。

最后一行包含一个整数 $K$（$0 \leq K \leq 100$）。

输入文件中的所有数字均为整数。

请注意：在 C++ 中读写 64 位整数时，请勿使用 %lld 格式说明符；推荐使用 cin（也可使用 %I64d）。

Print the required probability. Print the fractional number with such a precision that the relative or absolute error of the result won't exceed 10 - 9.

输出所需的概率。以分数形式输出该数值，要求结果的相对误差或绝对误差不超过 $10^{-9}$。