Грабёж
Честолюбивый Рой - грабитель, насмотревшись американских боевиков, заметил, что плохих праней всегда ловят в конце фильмов из-за их большой жадности. Поэтому он решил заняться своим прибыльным бизнесом по ограблению банков на короткий срок, после чего вернуться на комфортную работу в университет.
Уже несколько месяцев Рой оценивал системы безопасности нескольких банков, а также суммы наличных денег, хранящиеся там. Он хочет чтобы его риск был обдуманным, но при этом количество украденных денег было максимально возможным. Его мама Ольга вычислила приемлимое значение вероятности быть пойманным. Она чувствует, что ее сын будет в безопасности, если вероятность быть пойманным во всех ограбленных им банках будет меньше чем эта.
Входные данные
Первая строка содержит количество тестов 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.
Банк становится банкротом после ограбления, все вероятности независимы, так как у полиции слишком скудное финансирование.
Выходные данные
Для каждого теста в отдельной строке вывести наибольшее ожидаемое количество миллионов, которое может быть украдено, в то время как вероятность быть пойманным будет меньше заданной величины.