007 - 森田氏の欲求

問題文

「オナカスイタナニカタベタイ」
ダイエット中の某森田氏は、１日だけなら腹いっぱい食べてもいいか！と思い近くのお店に寄った。
その店中には森田氏が食べたいと思ったN個の商品がそれぞれ定価M[i]円で売られていた。

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

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

しかしお財布の中には、○○音声を大量に買ったせいであまり多くのお金がなかった。
そのため親友であり天才なあなたにN個の商品をすべて購入するときに、最小の購入金額の合計はいくらか計算してほしいと頼んできた。
商品を購入する順番は自由であるが、同時には購入できず1つずつしか購入できない。

入力

N
M[1]
M[2]
・
・
・
M[n]

入力は全て整数で与えられる。
1 <= N <= 15
1 <= M[i] <= 10000 商品iの定価の値段を表す。

出力

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

入出力例

入力例1

3
100
200
300

出力例1

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

出力例2

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

出力例3

10877