商品を前半 \(N/2\) 個と残りの後半に分け, それぞれ全探索してどの商品を買ったときに合計金額がいくらになるかを計算する. 後半については金額でソートしておく.

前半の買った商品ごとに残り後半でどの商品を買えばいいかを二分探索で求め, 買うべき商品のリストを答えの配列に入れていく.

最後に答えの配列をソートして出力する.