C. Закон первой цифры
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

В теории вероятностей известен следующий парадокс, называемый законом Бенфорда: «Во многих списках чисел из произвольных реальных источников, числа, начинающиеся с цифры 1, встречаются гораздо чаще, чем числа, начинающиеся с любой другой цифры» (это самая простая формулировка закона).

Ёжик, прочитав об этом на CodeForces, заинтересовался этим утверждением, и желает тщательно исследовать его. В частности, ему интересна следующая похожая задача: имеется N случайных величин, i-я из которых может равновероятно принимать любое целое значение из некоторого отрезка [Li;Ri]. Это означает, что значение i-ой величины может быть равно любому целому числу из заданного отрезка [Li;Ri] с вероятностью 1 / (Ri - Li + 1).

Ёжика интересует вероятность такого события, что первые цифры как минимум K% этих величин окажутся равными единице. Иными словами, зафиксируем какие-то значения этих случайных величин, и оставим от каждого значения только первую (старшую) цифру. Далее посчитаем, сколько раз среди этих первых цифр встретилась единица, и если она встретилась как минимум в K процентах из этих N величин, то такой набор значений величин назовём хорошим. Требуется найти вероятность того, что случайно выбранный набор будет хорошим.

Входные данные

В первой строке записано число N — размер списка (1 ≤ N ≤ 1000). Далее идут N строк, каждая из которых содержит по паре чисел Li, Ri — описание очередной случайной величины. Гарантируется, что 1 ≤ Li ≤ Ri ≤ 1018.

В последней строке записано целое число K (0 ≤ K ≤ 100).

Все числа во входном файле целые.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cin (также вы можете использовать спецификатор %I64d).

Выходные данные

Выведите искомую вероятность. Выводите это дробное число с такой точностью, чтобы относительная или абсолютная погрешность ответа не превышала 10 - 9.

Примеры
Входные данные
1
1 2
50
Выходные данные
0.500000000000000
Входные данные
2
1 2
9 11
50
Выходные данные
0.833333333333333