時間制限:1000ミリ秒
メモリ制限:10000KB
宇宙船函館丸
問題
観測宇宙船函館丸は、その無制限に詰める2つの燃料コンテナで有名である。それらはどちらも同じ種類の原子力燃料ボールを詰んでいる。
しかし、それには多少の不便があった。燃料コンテナ1番と2番はそれぞれ、立方体形と正四面体形をしている。それらはどちらも空であるか、または形にしたがって詰められている必要がある。さもなくば、燃料ボールは非常に不安定になり、燃料コンテナ内で爆発する可能性がある。そのため、コンテナ1番に積む燃料ボールの個数は立方数(n=0,1,2,3,...についてn^3)に、またコンテナ2番に積む燃料ボールの個数は四面体数(n=0,1,2,3,...についてn(n+1)(n+2)/6)にしなければならない。
函館丸は今、星基地五稜郭にて、星と星間の問題についての正確で詳細な地図を作るミッションのために準備をしている。五稜郭のパラス指揮官は、函館丸のフューチャー船長に、五稜郭が函館丸に供給できる燃料ボールの数を伝えた。フューチャー船長はパラス指揮官に、函館丸が五稜郭を去る前にいくつの燃料ボールをリクエストするかを伝えなければならない。もちろん、フューチャー船長と船員は、できるだけ多くの燃料ボールを積みたい。
例えば、パラス指揮官が151200個の燃料ボールの供給を提案したとしよう。もし燃料コンテナ1番のみが使用可能(つまり、燃料コンテナ2番が使用不可能)ならば、最大148877個(148877=53*53*53 < 151200 < 54*54*54)の燃料ボールを燃料コンテナに積むことができる。逆に、もし燃料コンテナ2番のみが使用可能ならば、最大147440個(147440=95*96*97/6 < 151200 < 96*97*98/6)の燃料ボールを燃料コンテナに積むことができる。燃料コンテナ1番と2番を両方使うとすると、151200個(151200=39*39*39+81*82*83/6)の燃料ボールを積むことができる。この場合は、フューチャー船長の答えは「151200」となるべきである。
五稜郭の燃料保管庫の限界のため、パラス指揮官が提案する燃料ボールの数は151200より多くなることはない。フューチャー船長と船員はそのことをよく知っている。
あなたは函館丸に配属されている燃料エンジニアである。あなたの今日の仕事は、フューチャー船長がリクエストするべき燃料ボールの数を計算することで彼女を助けることである。
入力
入力は最大でも1024個の正整数の列からなる。各行は1つの整数を含む。列のあとには0がある。これは入力の終わりを意味し、入力の一部としては扱われない。151200より大きい数が入力に出現することはないとしてよい。
出力
出力はいくつかの行からなり、各行は1つの整数を含む。各整数は、非負立方数と非負四面体数の和として考えられる値で、与えられた入力値を越えないもののうち最大のものである。それ以外の文字が出力に出現することはない。
入力例
100 64 50 20 151200 0
出力例
99 64 47 20 151200
出典
Japan 2001