#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1e9;
void chmax(int &a, int b){ if( a < b){ swap(a,b);} return ;}
const int MAX_N = 1<<16;
int dp[MAX_N];

int pre[20][20];

void chmin( int & a, int b){ if( a > b){ swap(a,b);} return ;}

int main(){
  int N; cin >> N; 
  vector<int> M(N);
  for(int i = 0; i < N; i++){ cin >> M[i];}
  
  for(int i = 0; i < MAX_N; i++){ dp[i] = inf;}
  dp[0] = 0; //何も商品を買わない時は、当然0円
  
  for(int mask = 0; mask < (1<<N); mask++){
    //ビットが立っている時、すでに購入済みのことを示す
    for(int a = 0; a < N; a++){
      //次に、商品aを購入する場合を考える
      if( !(mask >> a & 1)){
        
       int res = 0;
       for(int b = 0; b < N; b++){
         if( mask >> b & 1 ){ res += M[b];} res %= 1000;
       }
      
      chmin(dp[mask+(1<<a)],dp[mask]+(max(M[a]-res,0))%1000);}
  }
}

cout << dp[(1<<N)-1] << endl; return 0;}