오렌지 볼

오렌지 볼 미식축구 경기 종반, USC가 4점 차로 뒤지고 있어 반드시 터치다운을 하나 더 성공시켜야 한다. 그래서 감독은 프로그래밍 대회에서 작성된 새로운 무기, 곧 플레이 전략 평가기를 꺼내 든다.

미식축구는 복잡하지만 다음과 같이 단순화한다. USC는 현재 엔드존까지 $n$야드 떨어져 있다($1 \le n \le 100$). 감독은 공을 최대한 안전하게 엔드존까지 옮길 플레이 순서를 정해야 한다. 각 플레이마다 감독은 $m$가지 플레이 중 하나를 고를 수 있다($1 \le m \le 1000$). 각 플레이 $i$는 두 수로 표현된다. 전진 야드 $g_i$(정수, $1 \le g_i \le 100$)와 성공 확률 $p_i$(실수, $0 \le p_i \le 1$)이다. 플레이는 확률 $p_i$로 성공하며, 성공하면 USC를 엔드존 쪽으로 $g_i$야드 전진시키고, 실패하면 공격권을 잃어 USC가 패배한다.

전체 전진 야드가 $n$ 이상이면서 전체 성공 확률이 최대가 되도록 플레이 순서를 선택하라(같은 플레이를 반복해도 된다). 모든 플레이는 서로 독립적으로 성공하므로, 한 순서의 성공 확률은 각 플레이 확률의 곱이다.

(대회 원문의 농담: "USC가 미식축구 경기에서 뒤지는 일이 있을 리가.")

첫 줄에 데이터 집합의 개수 $K \ge 1$이 주어진다. 이어서 $K$개의 데이터 집합이 다음 형식으로 주어진다.

각 데이터 집합의 첫 줄에는 $n$과 $m$이 주어진다. 그 뒤로 $m$개의 줄이 이어지며, $i$번째 줄에는 플레이 $i$의 $g_i$와 $p_i$가 주어진다.

각 데이터 집합마다 먼저 "Data Set x:" 한 줄을 출력한다. 여기서 x는 데이터 집합의 번호(1부터 시작)이다. 그다음 줄에, 엔드존에 도달할 확률이 가장 높은 플레이 순서의 전체 성공 확률을 소수점 아래 둘째 자리까지 반올림하여 출력한다. 실제 플레이 순서는 출력할 필요가 없다.