No.286 Modulo Discount Store

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 183
作問者 : yuki2006yuki2006
2 ProblemId : 528 / 出題時の順位表

問題文

$N$個の商品がそれぞれ定価$M_i$円で売られているお店がある。

このお店で商品を購入する時、「今まで買った商品の"定価"の金額を合計して1000で割った余り($Mod\ 1000$)の料金分」を購入ごとに値引きしてくれるという。
ただし、購入する商品が値引き後0円未満になる場合は、0円で購入する。

あなたは、同じものを買わずに$N$個の商品を全て購入したいと思っている。

このとき$N$個の商品をすべて購入するときに、最小の購入金額の合計はいくらか計算してください。
商品を購入する順番は自由であるが、同時には購入できず1つずつしか購入できない。

入力

$N$
$M_1$
$M_2$
$\dots$
$M_N$

入力は全て整数で与えられる。
$1 \le N \le 15 $
$1 \le M_i \le 10000$ 商品$i$の定価の値段を表す。

出力

$N$個の商品をすべて購入するときに、最小の合計の購入金額はいくらか計算してください。

サンプル

サンプル1
入力
3
100
200
300
出力
200

商品$1$、商品$2$、商品$3$の順に購入する。

100円の商品$1$を購入する。この時、まだ何も買ってないので割引はない、100円で購入する。
200円の商品$2$を購入する。この時、商品$1$を購入しているので100円引きされ、(200-100=)100円で購入できる。
300円の商品$3$を購入する。この時、商品$1$,商品$2$を購入しているので300円引きされ、0円で購入できる。

よって、200円ですべて購入できる。

サンプル2
入力
3
1000
900
800
出力
1000

商品$2$、商品$1$、商品$3$の順に購入する。

900円の商品$2$を購入する。この時、まだ何も買ってないので割引はない、900円で購入する。
1000円の商品$1$を購入する。この時、商品$2$を購入しているので900円引きされ、100円で購入できる。
800円の商品$3$を購入する。この時、商品$1$,商品$2$を購入しているので900円引きされ
(割引額は今までの購入した定価の金額1900円の1000で割った余りの900円である)、0円で購入できる。

よって、1000円ですべて購入できる。購入する順番を入れ替えても1000円未満で購入する方法はない。

サンプル3
入力
5
10000
1000
100
10
1
出力
10877

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。