B. Темная Ассамблея
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Темная Ассамблея — это такой орган управления в Преисподней. Здесь заседают сенаторы, которые принимают самые важные для игрока решения. Например, для расширения ассортимента магазина или для улучшения некоторых характеристик персонажа необходимо одобрение Темной Ассамблеи.

В Темную Ассамблею входит n сенаторов. Каждый из них характеризуется уровнем и лояльностью к игроку. Уровень — это некоторое целое положительное число, которое отражает силу сенатора. Лояльность — это вероятность принятия положительного решения при голосовании, которая измеряется в процентах с точностью до 10%.

Сенаторы принимают решения посредством голосования. Каждый из них принимает положительное или отрицательное решение в соответствии со своей лояльностью. Если строго больше половины сенаторов принимают положительное решение, то предложение игрока утверждается.

Если после голосования предложение игрока не утверждается, то игрок может опротестовать решение Темной Ассамблеи. Для этого нужно убить всех сенаторов, что проголосовали против (в убийстве сенаторов нет ничего страшного, они потом воскреснут и будут еще хуже относиться к игроку). Вероятность того, что игроку удастся убить некоторую группу сенаторов, равна A / (A + B), где A — сумма уровней всех персонажей игрока, а B — сумма уровней всех сенаторов в этой группе. Если игрок убивает всех неугодных сенаторов, то предложение игрока утверждается.

Сенаторы очень любят конфеты. Их можно подкупить, раздав им конфеты. За каждую полученную конфету сенатор увеличивает свою лояльность к игроку на 10%. Стоит учесть, что выше 100% лояльность подняться не может. Игрок может взять с собой в зал заседания не более k конфет. Конфеты следует раздать до начала голосования.

Определите вероятность того, что Темная Ассамблея одобрит предложение игрока при оптимальном распределении конфет между сенаторами.

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

В первой строке находятся три целых числа n, k и A (1 ≤ n, k ≤ 8, 1 ≤ A ≤ 9999).

Далее идут n строк. i-ая из них содержит два числа — bi и li — уровень i-го сенатора и его лояльность.

Уровни всех сенаторов — целые числа в диапазоне от 1 до 9999 (включительно). Лояльности всех сенаторов — целые числа в диапазоне от 0 до 100 (включительно), все они делятся нацело на 10.

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

Выведите одно вещественное число с точностью 10 - 6 — максимальная возможная вероятность того, что Темная Ассамблея одобрит предложение игрока при оптимальном распределении конфет между сенаторами.

Примеры
Входные данные
5 6 100
11 80
14 90
23 70
80 30
153 70
Выходные данные
1.0000000000
Входные данные
5 3 100
11 80
14 90
23 70
80 30
153 70
Выходные данные
0.9628442962
Входные данные
1 3 20
20 20
Выходные данные
0.7500000000
Примечание

В первом примере выгоднее всего раздать все конфеты первым трем сенаторам — это дает гарантированное большинство голосов.

Во втором примере выгоднее всего отдать все три конфеты последнему сенатору.