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