포켓몬 인식 시스템

포켓몬의 종류는 아주 많다. 한 인증 기관이 포켓몬을 식별하는 영상 처리 장비를 만들고 있다. 장비의 기본 단위는 에이전트다. 에이전트는 카메라와 전용 알고리즘을 갖춘 장치로, 날개가 있는지, 꼬리가 있는지처럼 특징 하나만 판별한다. 중요하다고 정한 특징마다 전용 에이전트를 이미 설계해 두었다.

알고리즘은 완벽하지 않다. 포켓몬의 자세와 움직임에 따라 특징을 놓친다. 대신 거짓 양성은 나오지 않는다. 에이전트는 맡은 특징을 제대로 인식하거나 false를 돌려줄 뿐이다. 같은 종류의 에이전트를 여러 대 붙여 한 마리를 분석하면 각 에이전트가 특징을 놓칠 확률은 서로 독립이다. 그래서 종류마다 여러 대를 배치하면 그 특징의 신뢰도가 올라가고 시스템 전체의 신뢰도도 그대로 계산된다. 식별에 성공하려면 모든 종류의 에이전트에서 적어도 한 번은 인식에 성공해야 한다.

특징 $f$를 맡은 에이전트 한 대의 신뢰도가 $r_f$이고 이 종류를 $k$대 배치하면, 그 특징을 인식할 확률은 $1 - (1 - r_f)^k$이다. 시스템 전체의 신뢰도는 $F$개 특징의 확률을 모두 곱한 값이다.

예산 $B$, 특징의 수 $F$, 특징마다 에이전트 한 대의 가격 $c_f$와 신뢰도 $r_f$가 주어진다. 전체 신뢰도를 최대로 만드는 배치를 찾아라. 종류마다 최소 한 대는 배치해야 하고, 예산은 남겨도 된다.

입력은 여러 개의 문제로 이루어진다.

각 문제의 첫 줄에는 예산 $B$와 특징의 수 $F$가 주어진다. ($0 < B \le 10000$, $0 < F \le 30$)

이어지는 $F$개 줄에는 각 특징을 맡은 에이전트 한 대의 가격 $c_f$와 신뢰도 $r_f$가 주어진다. $c_f$는 양의 정수이고, $r_f$는 $0 \le r_f \le 1$인 실수다. 예산은 항상 모든 종류를 한 대씩 사기에 충분하다. 즉 $c_f$의 합은 $B$ 이하다.

마지막 줄에는 $0$ 두 개가 주어진다. 이 줄은 처리하지 않는다.

문제마다 한 줄에 최적 시스템의 비용과 전체 신뢰도를 공백으로 구분해 출력한다.

신뢰도는 반올림해 소수점 아래 정확히 네 자리로 적는다. 예를 들어 신뢰도가 $0.648$이면 0.6480으로 출력한다.

최대 신뢰도를 내는 배치가 여러 개면 그중 비용이 가장 작은 것을 출력한다. 테스트 데이터는 넷째 자리 반올림이 애매하지 않고 최적 비용이 배정밀도 계산의 오차에 흔들리지 않도록 골랐다.

특징이 세 개(날개, 꼬리, 다리)이고 예산이 $105$인 경우를 보자. 가격은 각각 $30$, $15$, $20$이고 신뢰도는 $0.9$, $0.8$, $0.5$이다.

최적 배치는 첫 번째 종류를 한 대, 나머지 두 종류를 두 대씩 두는 것이고 비용은 $30 \times 1 + 15 \times 2 + 20 \times 2 = 100$이다. 첫 번째 특징을 놓칠 확률은 $1 - 0.9 = 0.1$, 두 번째는 $(1 - 0.8)^2 = 0.04$, 세 번째는 $(1 - 0.5)^2 = 0.25$이다. 따라서 특징별 인식 확률은 $0.9$, $0.96$, $0.75$이고 전체 신뢰도는 $0.9 \times 0.96 \times 0.75 = 0.648$이다.