Пограбування
Честолюбивий Рой - грабіжник, надивившись американських бойовиків, помітив, що поганих хлопців завжди ловлять у кінці фільмів із-за їх великої жадібностиі Тому він вирішив зайнятися своїм прибутковим бізнесом з пограбування банків на короткий термін, після чого повернутись до комфортної работи в університеті.
Вже декілька місяців Рой оцінював системи безпеки декількох банків, а також суми наявних грошей, які зберігаються там. Він хоче щоб його ризик був обміркованим, але при цьому кількість вкрадених грошей була максимально можливою. Його мама Ольга обчислила допустиме значення ймовірності бути пійманим. Вона відчуває, що її син буде у безпеці, якщо ймовірність бути пійманим у всіх пограбуваних ним банках буде меншою ніж ця.
Вхідні дані
Первая строка содержит количество тестов T (0 < T ≤ 100). Для каждого теста в первой строке заданы действительное число P (0.0 ≤ P ≤ 1.0) - вероятность того что Рой будет пойман и целое число N (0 < N ≤ 100) - количество банков, которое он собрается ограбить. Дальше следуют N строк: j-ая строка содержит целое число M_j (0 < M_j ≤ 100) и действительное число P_j (0.0 ≤ P_j ≤ 1.0). Банк j содержит M_j миллионов, а вероятность быть пойманным при его ограблении равна P_j.
Банк становится банкротом после ограбления, все вероятности независимы, так как у полиции слишком скудное финансирование.
Вихідні дані
Для кожного теста у окремому рядку вивести найбільш очікувану кількість мільонів, які може бути вкрадено, в той час як ймовірність біти спійманим буде меншою заданої величини.