ある非負整数 \(x\) が与えられて、「\(x\) が、安い方から \(K\) 番目の金額以上であるか」という判定問題が時間計算量 \(\mathcal{O}(NK)\) くらいで解けたとしたら、この判定問題を使った二分探索で \(K\) 番目の金額がわかりそうです。

判定問題は次のような方法で解くことができます。

「頂点 \(0, 1, 2, ... x\) の \(x+1\) 個の頂点を持つグラフを考える。任意の頂点 \(v\) は \(v + A_i \leq x\) ならば頂点 \(v + A_i \) \((1\leq i\leq N)\) に向かう辺を持つ。頂点 \(0\) から到達可能な頂点が \(K\) 個を上回るかを実際に DFS して調べる。」

到達頂点数が \(K\) を上回ったら探索を打ち切るようにすれば、この DFS の計算量は \(\mathcal{O}(NK)\) 程度となりそうです。

二分探索は \(K\max{A_i}\) を解の上界に見積もってよさそうですから、全体として計算量は \(\mathcal{O}(NK\log{K\max{A_i}})\) 程度となり、定数倍に気をつけると通ります。

PyPy3 (2638 ms): https://atcoder.jp/contests/abc297/submissions/40486705