ACM International Collegiate Programming Contest
Japan Domestic, 2005-07-01


Problem A
Ohgas' Fortune

多賀家は八王子に代々続く名家として知られている.ことに,当主の多賀根餅 氏は著名な大資産家で,手元の資金を運用会社に預けてできるだけ増やしたい と考えている.あなたが多賀氏から依頼されたのは,託された資金を定められ た期間運用し,最大の利益を得られるようにすることである.

選択肢として複数の運用方法が提示される.あなたはその中から 一つの運用方法を選び,託された運用資金すべてを定められた期間,その 方法で運用する. 各運用方法につき,年利率,複利か単利かの別,毎年の手数料が定まっている. 手数料は運用している資金の量によらず定額である. 毎年の終わりに利子がつく.利子は,現在の運用資金の残高に年利率をかけ,1円 未満を切り捨てることで計算される.複利の場合,利子は翌年以降の運用資金の残高に 加算される.単利の場合,利子は別の場所へ蓄積され,運用資金の残高に は加えない(つまり,今後の利子の対象とならない). そして,運用資金の残高から手数料が徴収される.ここで,手数料が払えない (運用資金の残高が手数料を下回る)ことはないと仮定してよい. 運用期間終了後に手にする,「最終資金」とは,単利の場合は最終年の終わり における運用資金の残高と,蓄積された利子の和のことであり,複利の場合は 単に,最終年の終わりにおける運用資金の残高のことである.

運用会社は,C, C++, Javaなどを用いて資金計算を行っているため,年 利率に対して特別な注意を払っている. すなわち,年利率は0.0001220703125以上0.125以下の,0.0001220703125の倍 数である.0.0001220703125は,1/8192を十進小数で表示したものであり,年 利率がこの倍数であるということは,つまり,二進表現の倍精度浮動小数点数として 年利率を,誤差なく表現できることを意味している.

たとえば100万円の資金を年利率0.03125 (3.125%)の複利, 毎年の手数料3000円で5年間運用すると,毎年の運用資金の残高は以下のようになる.

運用資金の残高(年始)利子運用資金の残高(年末)
AB = A × 0.03125 (1円未満切捨て) A + B - 3000
1000000312501028250
1028250321321057382
1057382330431087425
1087425339821118407
1118407349501150357

この方法では,5年後の最終資金は1150357円となる.

同じ設定で単利の場合,以下のようになる.

運用資金の残高(年始)利子運用資金の残高(年末)利子累計
AB = A × 0.03125 (1円未満切捨て)A - 3000
10000003125099700031250
9970003115699400062406
9940003106299100093468
99100030968988000124436
98800030875985000155311

この場合,運用資金の残高985000円と利子累計155311円を合計した, 1140311円が最終資金になる.

Input

入力はいくつかのデータセットが並んだものである.全体としては以下 のような形式になる.

データセット数(=m)
データセット1の記述
データセット2の記述
...
データセットmの記述

「データセット数」mは100を越えないものとする. 各「データセット」の記述は以下の形式をしている.

初期運用資金量
運用年数
運用方法の種類数(=n)
運用方法1の記述
運用方法2の記述
...
運用方法nの記述

「初期運用資金量」,「運用年数」,「運用方法の種類数」nはいずれも正整数で, 資金量は1億を,運用年数は10を,種類数は100を越えることはない.

各「運用方法」の記述は以下の形式をしている.

単利・複利の別 年利率 毎年の手数料  

「単利・複利の別」は0または1の1文字で,0が単利,1が複利を表す. 「年利率」は十進小数で表され,上に述べたように,1/8192の倍数である. 「毎年の手数料」は非負の整数で,100000を越えることはない.

Output

各データセットについて,最大の最終資金(最終資金を最大にする運用方法の 最終資金)を,十進の整数値として,それぞれ1行に出力しなさい.各出力行は この数値以外の文字を含んではならない.

最終資金が,与えられた運用資金以上になる運用方法が最低でも一つ存在す ることが保証されている.また,最適な運用を選んだ場合でも,最終残高が10 億を越えることはないことが保証されている.

Sample Input

4
1000000
5
2
0 0.03125 3000
1 0.03125 3000
6620000
7
2
0 0.0732421875 42307
1 0.0740966796875 40942
39677000
4
4
0 0.0709228515625 30754
1 0.00634765625 26165
0 0.03662109375 79468
0 0.0679931640625 10932
10585000
6
4
1 0.0054931640625 59759
1 0.12353515625 56464
0 0.0496826171875 98193
0 0.0887451171875 78966

Output for the Sample Input

1150357
10559683
50796918
20829397

First Input Data

ここに1番目のデータ がある.


The ACM ICPC