\(i\) 番目の商品を \(k\) 個購入するとき \(k^2P_i\) 円かかるというのを以下のように言い換えることができます。

• \(i\) 番目の商品の値段はそれぞれ異なり、\(j\) 番目 (1-indexed) に安いものの値段は \((2j-1)P_i\) 円である。

例えば、\(P_i=2\) のとき商品の値段は \(2,6,10,14,\ldots\) となっています。この言い換えの正当性は、\(k\) 個購入するときは安いもの \(k\) 個を購入すること、及び \(\sum_{i=1}^k (2i-1) = k^2\) という等式が成立することから示せます。

言い換え後の問題を解きます。\(N\times 10^{100}\) 個の商品それぞれの値段が分かり、その中で安いものから順に買えるだけ買うことで購入する個数の最大化ができますが、当然全ての商品の値段の列挙及びソートは行えません。

ここで、安いものから購入する方法は以下の特徴を持ちます。

• ある整数 \(x\) が存在し、値段が \(x\) 以下の商品を全て購入し、値段が\(x+1\) の商品を買えるだけ購入している。

この \(x\) は二分探索により求めることができます。そして、この \(x\) が分かれば購入できる個数の最大値も求めることができます。オーバーフローには十分注意してください。

計算量は \(\mathrm{O}(N\log M)\) です。