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=a[j]<m?0:a[j]-m,!d[k=i^1<<j]|d[k]>d[i]+m?d[k]=d[i]+m:0)for(m=0,k=16;k--;m%=1000)m+=(~i>>k&1)*a[k];i=!printf("%d",*d);}