d[99999],a[20],i,j,k,n;
main(m){
	for(gets(&m);~scanf("%d",a+n);n++);
	for(;i<1<<n;i++){
		for(j=0;j<n;j++){
			if(i>>j&1)continue;
			for(m=k=0;k<n;k++)m=(m+(i>>k&1)*a[k])%1000;
			m=a[j]<m?0:a[j]-m;
			!d[i^1<<j]|d[i^1<<j]>d[i]+m?d[i^1<<j]=d[i]+m:0;
		}
	}
	i=!printf("%d",d[(1<<n)-1]);
}