No.286 Modulo Discount Store
yuki2006問題文
$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
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。