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

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

// 今までに買った商品たちの定価の合計
int sum_of(int mask) {
  int res = 0;
  for(int i=0; i<n; i++) {
    if(mask>>i & 1) { res += m[i]; }
  }
  return res;
}

// 買った商品の集合がmask
// そのときの値引きの最大金額を返す
int rec(int mask) {
  int &res = dp[mask];
  // 何も買ってないので値引きは無い。
  if(mask == 0) { return res = 0; }
  if(res > 0) { return res; }
  // i番目を買う前の時点に話を戻したい
  for(int i=0; i<n; i++) {
    if(!(mask>>i & 1)) { continue; } // i番目を買ってないから話を戻せない
    // i番目を買うときの値引き額は
    // "i番目を買う前"の買った商品たちの定価の合計から算出する
    res = max(res, rec(mask&~(1<<i)) + min(m[i], sum_of(mask&~(1<<i)) % mod));
  }
  return res;
}

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

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

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

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

int main(void) {
  scanf("%d", &n);
  m.resize(n);
  int allsum = 0;
  for(int i=0; i<n; i++) {
    scanf("%d", &m[i]);
    allsum += m[i];
  }
  dp.resize(1<<n, 0);
  for(int mask=0; mask<1<<n; mask++) {
    for(int i=0; i<n; i++) {
      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;
}