은행 강도

로이는 짧은 기간만 은행을 털고 대학의 편안한 자리로 물러날 생각이다. 몇 달 동안 은행마다 현금이 얼마나 있는지, 털었을 때 잡힐 위험이 얼마나 되는지 조사했다.

어머니 올라는 견딜 수 있는 위험의 한계를 정해 두었다. 로이는 은행을 원하는 대로 골라 털 수 있고 같은 은행은 최대 한 번만 턴다. 다만 잡힐 확률이 이 한계보다 반드시 작아야 한다. 은행마다 잡히는 사건은 서로 독립이므로 집합 $S$에 속한 은행을 털면 잡힐 확률은 $1 - \prod_{j \in S} (1 - P_j)$이다.

로이가 가져올 수 있는 금액의 최댓값을 구하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 실수 $P$와 정수 $N$이 주어진다. $P$는 로이가 넘지 말아야 할 한계이고, $N$은 그가 계획해 둔 은행의 수이다. 이어지는 $N$개의 줄에는 정수 $M_j$와 실수 $P_j$가 주어진다. 은행 $j$에는 $M_j$백만이 있고, 이 은행을 털 때 잡힐 확률은 $P_j$이다.

• $0 < T \le 100$
• $0.0 \le P \le 1.0$
• $0 < N \le 100$
• $0 < M_j \le 100$
• $0.0 \le P_j \le 1.0$
• 입력의 모든 실수는 소수점 아래 두 자리 이하이다.

털린 은행은 곧바로 파산하므로 같은 은행을 두 번 털지 않는다.

각 테스트 케이스마다 잡힐 확률을 $P$보다 작게 유지하면서 가져올 수 있는 최대 금액을 백만 단위로 한 줄에 출력한다. 조건을 만족하는 선택이 없으면 0을 출력한다.