整数列に対し、部分列の要素の和となりうる整数を以下では単に部分和とよびます。

\(A_i\) はソートして昇順とします。

集合 \(EX_i\) を \(S_i :=A_1+A_2+\dots+A_i\) 以下の非負整数のうち、\((A_1,A_2,\dots,A_i)\) の部分和ではない非負整数からなる集合とします。便宜上、\(EX_0=\{\}\) とし、\(EX_{i-1}\) から \(EX_i\) を求めていくことを考えます。\(A\) の値によっては \(EX_i\) はかなり大きな集合になってしまいそうです。しかし、実は 「\(EX_{N}\) に属する整数のうち小さいほうから \(K\) 個が確定」するまでの間はそこまでおおきくならず、\(|EX_i| \leq Ki\) が成り立ちます。以下ではこれを帰納的に示します。

\(EX_{i-1}\) に対する \(EX_i\) について、以下のように場合分けして考えます。

[1] \(S_{i-1} < A_i\) の場合

\(A\) の単調性から

• \(EX_{i-1}\) に属する整数
• \(S_{i-1}+1\) 以上 \(A_i\) 未満の整数

は \(A\) の部分和になりえないことが確定します。さらに、\(EX_N\) の要素のうち \(A_i\) 未満の整数はこれですべてです。このような整数の個数は \(|EX_{i-1}| + A_i-S_{i-1}-1\) 個であり、これが \(K\) 個以上である場合は求める \(K\) 個の整数が確定します（★）。

\(K\) 個以上でない場合を考えます。\(EX_i\) は

• \(EX_{i-1}\) に属する整数
• \(S_{i-1}+1\) 以上 \(A_i\) 未満の整数
• \(A_i\) 以上 \(S_i\) 未満の整数 \(x\) であって、 \(x-A_i \in EX_{i-1}\) であるもの

の \(3\) 種類の整数に分けることができます。\(2,3\) 種類目の整数の個数は \(|EX_{i-1}|+A_i-S_{i-1}-1\) 個であり、これは \(K\) 個未満であるとしたため \(|EX_i| \leq |EX_{i-1}|+K\) が成り立ちます。

[2] \(A_i \leq S_{i-1}\) の場合

\(A\) の単調性から

• \(A_i\) 未満の整数であって、\(EX_{i-1}\) に属する整数

は \(A\) の部分和になりえないことが確定します。さらに、\(EX_N\) の要素のうち \(A_i\) 未満の整数はこれですべてです。このような整数の個数が \(K\) 個以上である場合は求める \(K\) 個の整数が確定します（★）。

\(K\) 個以上でない場合を考えます。 \(EX_i\) は

• \(A_i\) 未満の整数であって、\(EX_{i-1}\) に属する整数
• \(A_i\) 以上 \(S_{i-1}\) 以下の整数 \(x\) であって、 \(x \in EX_{i-1}\) かつ \(x-A_i \in EX_{i-1}\) を満たす整数
• \(S_{i-1}+1\) 以上 \(S_i\) 以下の整数 \(x\) であって、\(x-A_i \in EX_{i-1}\) を満たす整数

の \(3\) 種類の整数に分けることができます。\(1,2\) 種類目の整数は \(EX_{i-1}\) の要素であり、個数は \(|EX_{i-1}|\) 以下です。\(3\) 種類目の整数の個数については \(x \in EX_{i-1} \iff S_{i-1}-x \in EX_{i-1}\) に注意すると \(1\) 種類目の整数の個数と同じであり、これは \(K\) 個未満であるとしたため \(|EX_i| \leq |EX_{i-1}|+K\) が成り立ちます。

以上より★のように答えが確定しない間は \(|EX_i| \leq |EX_{i-1}| + K\) が成り立つので、帰納的に \(|EX_i| \leq Ki\) が成り立つことがわかります。

よって★のような状況ではすぐに答えを出力するようにしつつ、\(EX_i\) を愚直に保持しておくと（std::set で保持した場合） \(O(N^2K\log {(NK)})\) で答えが求まります。