Хабар
Після того, як ви провели багато шпигунських операцій та проникли в кримінальну мережу, ви готові спробувати її знищити. Це, однак, вимагає співпраці певної кількості поплічників, яких потрібно підкупити, але через обмежений бюджет у вас є лише певна сума грошей.
На щастя, ви добре розбираєтеся в людях, тому для кожного з поплічників, яких ви розглядаєте для підкупу, ви знаєте, яку суму грошей вони вимагатимуть. Крім того, ви знаєте ймовірність того, що вони успішно перейдуть на вашу сторону, а не просто візьмуть гроші і втечуть. Час не підганяє, тому після кожної спроби конверсії ви можете перевірити, чи була вона успішною, перш ніж перейти до наступного. Звісно, якщо спроба не вдалася, ви не можете підкупити цього поплічника вдруге.
Маючи всю цю інформацію про поплічників, суму грошей, яку ви маєте, і кількість поплічників, яких потрібно конвертувати, чи зможете ви визначити ймовірність успішного завершення операції?
Вхідні дані
На першому рядку одне позитивне число: кількість тестових випадків, не більше 100. Після цього для кожного тестового випадку:
один рядок з трьома цілими числами, розділеними пробілами: n, c та m (1 ≤ n, c ≤ 16 та 1 ≤ m ≤ 1000): кількість поплічників, яких можна підкупити, кількість, яку потрібно конвертувати, та сума грошей, яку ви маєте, відповідно.
n рядків з двома цілими числами, розділеними пробілами: b та p (0 ≤ b ≤ 1000 та 0 ≤ p ≤ 100): сума грошей, необхідна для підкупу кожного поплічника, та ймовірність (у відсотках), що він буде успішно конвертований, відповідно.
Вихідні дані
Для кожного тестового випадку:
один рядок з одним числом з плаваючою комою: ймовірність того, що вам вдасться конвертувати c поплічників, якщо ви оберете оптимальний підхід. Це число має бути точним до 10^{-6} відносної або абсолютної точності.