득표수 최대화 선거 자금 배분

밥 테스트(Bob Test)는 커닝(Kerning) 마을의 시장 선거에 출마했다. 커닝은 여러 개의 선거구(0, 1, 2, ... 번)로 나뉘어 있고, 밥은 광범위한 여론조사를 통해 각 선거구에서 자신에게 투표하려는 유권자의 현재 비율을 알고 있다. 그는 모든 선거구에서 이 비율을 높이고 싶지만, 쓸 수 있는 돈이 한정되어 있다.

과거 결과에 따르면, 한 선거구에 돈을 쓸 때의 효과는 다음 식을 따른다.

$$F_p = I_p + \left(\frac{M}{10.1 + M}\right)\Delta$$

여기서 $I_p$는 현재 밥에게 투표하려는 유권자의 비율(퍼센트), $\Delta$는 이 비율을 최대로 올릴 수 있는 증가량, $M$은 그 선거구에 쓴 돈으로 $1 단위의 음이 아닌 정수이며, $F_p$는 그 결과로 기대되는 비율이다. 밥이 얻는 총 득표수가 최대가 되도록 돈을 어떻게 써야 하는지 구하라.

각 테스트 케이스의 첫 줄에는 두 정수 $m$과 $n$이 주어진다. $m$은 밥이 쓸 수 있는 돈(달러), $n$은 선거구의 수이며, 둘 다 최대 $100$이다. 이어지는 $n$개의 줄에는 각각 $N\ I_p\ \Delta$ 형태로 모두 양의 정수가 주어져 한 선거구의 정보를 나타낸다. $N$은 그 선거구의 인구($10000$ 미만)이고, $I_p$와 $\Delta$는 위에서 설명한 값이다. 이 줄들 중 첫째 줄이 선거구 0, 다음 줄이 선거구 1, ... 을 나타낸다.

마지막 테스트 케이스 다음에는 0 0인 줄이 온다.

한 선거구의 밥 지지 유권자 수를 구할 때에는, 먼저 위 식으로 $F_p$를 부동소수점으로 계산한 뒤, 그 비율에 인구 $N$을 곱하고($F_p \times N / 100$) 가장 가까운 정수로 반올림한다. 이때 $0.5$는 올림한다.

각 테스트 케이스마다 두 줄을 출력한다. 첫 줄에는 케이스 번호와 최적으로 돈을 썼을 때 밥이 얻을 수 있는 최대 득표수를 출력한다. 둘째 줄에는 각 선거구에 밥이 써야 할 금액을 선거구번호:금액 형식으로 쓰고, 각 쌍을 공백 하나로 구분하여 출력한다.

Case X: votes
0:money0 1:money1 ...

최대 득표수를 내는 방법이 여러 가지라면, 선거구 0에 가장 많이 쓰는 방법을 출력한다. 선거구 0에 같은 금액을 쓰는 방법이 여럿이면 그중 선거구 1에 가장 많이 쓰는 방법을 택하고, 그다음도 마찬가지로 한다.