#include"bits/stdc++.h"

//#include<bits/stdc++.h>
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a) for(int i=0;i<a;i++)
typedef long long ll;
const ll mod = 10000000000;

int n;
int m[16];
int dp[65537][1000];//これまで取ったものの集合と合計値段のmodでこれからいくらかかるかの最小値
int rec(int s,int p) {
	if (dp[s][p] > 0)return dp[s][p];
	if (s == (1 << n) - 1)return dp[s][p] = 0;
	int res = mod;
	REP(u, n) {
		if (!(s >> u & 1)) {
			res = min(res, rec(s | 1 << u, (p + m[u]) % 1000) + max(0, m[u] - p % 1000));
		}
	}
	return dp[s][p] = res;
}

int main() {
	cin >> n;
	REP(i, n)cin >> m[i];
	memset(dp, -1, sizeof(dp));
	print(rec(0,0));
	return 0;
}