#include<bits/stdc++.h>
using namespace std;

const long long inf=1e9;
int A[21];
int dp[1<<21];

int main(void){

    long long n;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> A[i];
    }
    for(int i=0;i<(1<<21);i++){
        dp[i]=inf;
    }
    dp[0]=0;
    //　1は選択済み。0はこれから
    for(int msk=0; msk<(1<<n); msk++){
      for(int j=0; j<n; j++){
        if(!(msk & (1<<j))){//まだ選択してない
          int total = 0;
          for(int i=0;i<n;i++){
            if(msk & (1<<i)) total += A[i];
          }
          dp[msk+(1<<j)]= min(dp[msk+(1<<j)],dp[msk]+max(0,A[j]-(total%1000)));
        }
      }
    }

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