#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;
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 main(void) {
  scanf("%d", &n);
  m.resize(n);
  int allsum = 0;
  for(int i : range(n)) {
    scanf("%d", &m[i]);
    allsum += m[i];
  }
  dp.resize(1<<n, 0);
  for(int mask : range(1<<n)) {
    for(int i : range(n)) {
      if(mask>>i & 1) { continue; }
      int &tmp = dp[mask|(1<<i)];
      int val = dp[mask] + min(m[i], sum_of(mask) % mod);
      tmp = max(tmp, val);
    }
  }
  int res = allsum - dp[(1<<n)-1];
  printf("%d\n", res);
  return 0;
}