#include <iostream>
#include <algorithm>
using namespace std;

class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};

const int mod = 1000;
int n, allsum;
vector<int> m, dp;

int sum_of(int mask) {
  int res = 0;
  for(int i : range(n)) {
    if(mask>>i & 1) { res += m[i]; }
  }
  return res;
}

int rec(int mask) {
  int &res = dp[mask];
  if(__builtin_popcount(mask) == n) { return res = 0; }
  if(res > 0) { return res; }
  for(int i : range(n)) {
    if(mask>>i & 1) { continue; }
    res = max(res, rec(mask|(1<<i)) + min(m[i], sum_of(mask) % mod));
  }
  return res;
}

int main(void) {
  scanf("%d", &n);
  m.resize(n);
  for(int i : range(n)) {
    scanf("%d", &m[i]);
    allsum += m[i];
  }
  dp.resize(1<<n);
  int discount = rec(0);
  printf("%d\n", allsum-discount);
  return 0;
}