問題文
「オナカスイタナニカタベタイ」
ダイエット中の某森田氏は、１日だけなら腹いっぱい食べてもいいか！と思い近くのお店に寄った。
その店中には森田氏が食べたいと思った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