ACM International Collegiate Programming Contest
Japan Domestic, 2005-07-01
多賀家は八王子に代々続く名家として知られている．ことに，当主の多賀根餅 氏は著名な大資産家で，手元の資金を運用会社に預けてできるだけ増やしたい と考えている．あなたが多賀氏から依頼されたのは，託された資金を定められ た期間運用し，最大の利益を得られるようにすることである．
選択肢として複数の運用方法が提示される．あなたはその中から 一つの運用方法を選び，託された運用資金すべてを定められた期間，その 方法で運用する． 各運用方法につき，年利率，複利か単利かの別，毎年の手数料が定まっている． 手数料は運用している資金の量によらず定額である． 毎年の終わりに利子がつく．利子は，現在の運用資金の残高に年利率をかけ，1円 未満を切り捨てることで計算される．複利の場合，利子は翌年以降の運用資金の残高に 加算される．単利の場合，利子は別の場所へ蓄積され，運用資金の残高に は加えない(つまり，今後の利子の対象とならない)． そして，運用資金の残高から手数料が徴収される．ここで，手数料が払えない (運用資金の残高が手数料を下回る)ことはないと仮定してよい． 運用期間終了後に手にする，「最終資金」とは，単利の場合は最終年の終わり における運用資金の残高と，蓄積された利子の和のことであり，複利の場合は 単に，最終年の終わりにおける運用資金の残高のことである．
運用会社は，C, C++, Javaなどを用いて資金計算を行っているため，年 利率に対して特別な注意を払っている． すなわち，年利率は0.0001220703125以上0.125以下の，0.0001220703125の倍 数である．0.0001220703125は，1/8192を十進小数で表示したものであり，年 利率がこの倍数であるということは，つまり，二進表現の倍精度浮動小数点数として 年利率を，誤差なく表現できることを意味している．
たとえば100万円の資金を年利率0.03125 (3.125%)の複利， 毎年の手数料3000円で5年間運用すると，毎年の運用資金の残高は以下のようになる．
| 運用資金の残高(年始) | 利子 | 運用資金の残高(年末) |
| A | B = A × 0.03125 (1円未満切捨て) | A + B - 3000 |
| 1000000 | 31250 | 1028250 |
| 1028250 | 32132 | 1057382 |
| 1057382 | 33043 | 1087425 |
| 1087425 | 33982 | 1118407 |
| 1118407 | 34950 | 1150357 |
この方法では，5年後の最終資金は1150357円となる．
同じ設定で単利の場合，以下のようになる．
| 運用資金の残高(年始) | 利子 | 運用資金の残高(年末) | 利子累計 |
| A | B = A × 0.03125 (1円未満切捨て) | A - 3000 | |
| 1000000 | 31250 | 997000 | 31250 |
| 997000 | 31156 | 994000 | 62406 |
| 994000 | 31062 | 991000 | 93468 |
| 991000 | 30968 | 988000 | 124436 |
| 988000 | 30875 | 985000 | 155311 |
この場合，運用資金の残高985000円と利子累計155311円を合計した， 1140311円が最終資金になる．
入力はいくつかのデータセットが並んだものである．全体としては以下 のような形式になる．
データセット数(=m)
データセット1の記述
データセット2の記述
...
データセットmの記述
「データセット数」mは100を越えないものとする． 各「データセット」の記述は以下の形式をしている．
初期運用資金量
運用年数
運用方法の種類数(=n)
運用方法1の記述
運用方法2の記述
...
運用方法nの記述
「初期運用資金量」，「運用年数」，「運用方法の種類数」nはいずれも正整数で， 資金量は1億を，運用年数は10を，種類数は100を越えることはない．
各「運用方法」の記述は以下の形式をしている．
単利・複利の別 年利率 毎年の手数料
「単利・複利の別」は0または1の1文字で，0が単利，1が複利を表す． 「年利率」は十進小数で表され，上に述べたように，1/8192の倍数である． 「毎年の手数料」は非負の整数で，100000を越えることはない．
各データセットについて，最大の最終資金(最終資金を最大にする運用方法の 最終資金)を，十進の整数値として，それぞれ1行に出力しなさい．各出力行は この数値以外の文字を含んではならない．
最終資金が，与えられた運用資金以上になる運用方法が最低でも一つ存在す ることが保証されている．また，最適な運用を選んだ場合でも，最終残高が10 億を越えることはないことが保証されている．
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
1150357 10559683 50796918 20829397
ここに1番目のデータ がある．
The ACM ICPC