We assume that buying nothing for \(0\) yen is allowed, by firstly incrementing \(K\) by one.

The \(K\)-th cheapest combination do not buy more than \(K\) copies of takoyaki of a single kind, so one can exhaustively iterate the number of takoyakis of each kind between \(0\) and \(K\) to solve this problem in a total of \(O(K^N)\) time; however, this does not fit in the execution time limit, so we need to device a better iteration.

Suppose that we know the prices of \(i\) cheapest combinations. The price of the \((i+1)\)-th is obtained by adding any takoyaki to one of the \(i\) ways; otherwise, retaining only one takoyaki of the added kind and removing the others yield a cheaper way of buying.

Therefore, the following search solves this problem.

• First, prepare a data structure \(Q\) that manages a set that initially contains \(0\), and an array \(\mathrm{ans}\) of length \(K\) that stores the answers. For each \(i=2,3,\dots,K\) in this order:
  • Obtain the smallest value \(v\) in \(Q\), and let \(\mathrm{ans}[i]=v\). Here, if \(\mathrm{ans}[i-1]=v\), inspect the next element.
  • For each \(j=1,2,\dots,N\), insert \((v+A_j)\) to \(Q\).

We advance to the next element if \(\mathrm{ans}[i-1]=v\) so that the same price is counted only once.

The complexity is \(\mathrm{O}(K N \log (NK))\) because we access \(Q\) \((K \times N)\) times, which is fast enough.

One can remove the maximum value of \(Q\) while the size of \(Q\) exceeds \(K\) to reduce the complexity to \(\mathrm{O}(K N \log K)\).

The searching algorithm above is almost identical to Dijkstra’s algorithm: it is as if we perform Dijkstra’s algorithm on a graph whose vertices are the combinations of takoyakis and whose edges are the price of each takoyaki. Note however that combinations with the same price are regarded the same.