お菓子の詰め合わせ C#編（paizaランク A 相当）

これは、A ランクの問題としてスキルチェックに出題されていた問題です。試しに解いてみましょう。
現時点では自力で正解することができない場合は、この問題を飛ばして次の問題に進んでください。
この問題の後に続く 3 つの問題に順番に取り組むことで、
この問題を解くために必要な知識や考えた方を身につけることができます。
A ランク獲得に向けた学習にお役立てください。

A 君は学校の遠足に持っていくお菓子を買わなければなりません。しかし、学校のルールにより、お菓子の総額は指定範囲内に収めなければなりません。
そこで、指定金額ギリギリまで使って、なるべく色々な種類のお菓子を食べたいと思った A 君は買うお菓子を決めるために、学校のルールと自分の要望を踏まえて以下の基準を満たす買い方をすることにしました。

・お菓子の総額を指定範囲内

・種類の数を最大にする

・同じお菓子は複数買わない

・お釣りを最小

・お釣りを最小にすることよりも種類の数を最大にすることを優先する

お菓子の値段が書いてあるリストが与えられるので、A 君の代わりに、上記ルールを満たすお菓子の組み合わせを指定範囲内の最大の金額で買ったときのお釣りを求めてください。ただし、少なくとも一種類は指定範囲の値段で買えるものとします。

入力例 1 の場合は、以下のように、指定範囲の金額で最大 2 個買えます。そして、そのうち最小になるお釣りの金額は 20 円になります。