That buying \(k\) instances of the \(i\)-th product costs \(k^2P_i\) yen means:

• each instance of the \(i\)-th product has a different price; the \(j\)-th (1-based indexing) cheapest instance costs \((2j-1)P_i\) yen.

For example, if \(P_i=2\), the costs are \(2,6,10,14,\ldots\). This interpretation is valid because we always choose the \(k\) cheapest instances when buying \(k\) instances, and by the equation \(\sum_{i=1}^k (2i-1) = k^2\).

We will solve the rephrased problem. Now we know the prices of the \(N\times 10^{100}\) items, where we can maximize the number of items to buy by picking from the cheapest, but of course, we cannot enumerate all the prices of the items and sort them.

Here, the cheap-first strategy has the following property:

• there exists an integer \(x\) such that we buy all the items with price at most \(x\), as well as as many items of price \(x+1\) as possible.

This \(x\) can be found with binary search. Once we find this \(x\), the maximum number of items that can be bought is also found. Be very careful of overflows.

The complexity is \(\mathrm{O}(N\log M)\).