Рабочее место участника

Прибор состоит из нескольких блоков. Для каждого блока известна вероятность его безотказной работы в течение определённого времени (надежность). Если хотя бы один из блоков прибора выходит из строя, перестаёт работать весь прибор, в связи с этим вероятность безотказной работы всего прибора `P` находится как произведение надёжностей его блоков: `P\ =\ p_1⋅p_2⋅…⋅p_N`. Для повышения надёжности прибора было принято решение выполнить резервирование некоторых блоков. Резервирование блока – это подключение параллельно к нему одного или нескольких таких же блоков. При аварии первого блока его функции будет выполнять второй, и т.д., на надёжность всех остальных блоков эта замена не повлияет. Будем считать, что вероятность безотказной работы группы из `K` одинаковых блоков (включая исходный) находится следующим образом: `p'=1-(1-p)^K`, где `p` – вероятность безотказной работы одного такого блока. Вероятность безотказной работы прибора тогда определится как `P'\ =\ p'_1⋅p'_2·…⋅p'_N`. Известна стоимость каждого блока и сумма `S`, выделенная на модернизацию всего прибора.

Требуется найти максимальную вероятность безотказной работы прибора, которую мы можем получить при условии, что суммарная стоимость добавленных блоков не должна превышать `S`.

В первой строке входного файла находится целое число `N` (`1\ ≤\ N\ ≤\ 30`) – количество блоков в приборе. В следующих `N` строках через пробел записано по два числа – вероятность безотказной работы очередного блока `p_i` и его стоимость `s_i` (`p_i` – вещественное число, `0\ <\ p_i\ ≤\ 1`, `s_i` – целое число, `1\ ≤\ s_i\ ≤1000`). В следующей строке записано целое число `S` (`0\ ≤\ S\ ≤\ 1000`) – сумма, выделенная на модернизацию прибора.

В первую строку выходного файла выведите одно число – вероятность безотказной работы прибора после модернизации с пятью десятичными цифрами после запятой.

3
0.6 10
0.7 14
0.8 8
30

0.62899