Взятка
После проведения множества шпионских операций и внедрения в преступную сеть, вы готовы попытаться её разобрать. Для этого необходимо сотрудничество определённого числа подручных, которых нужно подкупить. Однако, из-за сокращения бюджета у вас есть ограниченное количество средств.
К счастью, вы отлично разбираетесь в людях, поэтому знаете, какую сумму денег запросит каждый из подручных, которых вы рассматриваете для подкупа. Более того, вы знаете вероятность того, что они успешно перейдут на вашу сторону, а не просто возьмут деньги и сбегут. Спешки нет, поэтому после каждой попытки перевербовки вы можете определить, была ли она успешной, прежде чем перейти к следующему подручному. Конечно, если попытка не удалась, вы не можете подкупить этого подручного повторно.
Имея всю эту информацию о подручных, сумму денег, которая у вас есть, и количество подручных, которых нужно перевербовать, можете ли вы вычислить вероятность успешного завершения операции?
Входные данные
На первой строке указано одно положительное число: количество тестовых случаев, не более 100. Далее для каждого тестового случая:
одна строка с тремя целыми числами, разделёнными пробелами: n, c и m (1 ≤ n, c ≤ 16 и 1 ≤ m ≤ 1000): количество подручных, которых можно подкупить, количество, которое нужно перевербовать, и сумма денег, которая у вас есть, соответственно.
n строк с двумя целыми числами, разделёнными пробелами: b и p (0 ≤ b ≤ 1000 и 0 ≤ p ≤ 100): сумма денег, необходимая для подкупа каждого подручного, и вероятность (в процентах), что он будет успешно перевербован, соответственно.
Выходные данные
Для каждого тестового случая:
одна строка с одним числом с плавающей запятой: вероятность того, что вам удастся перевербовать c подручных, если вы выберете оптимальный подход. Это число должно быть точным до 10^{-6} относительной или абсолютной точности.