package no286; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] a = new int[n]; for(int i=0;i<n;i++) { a[i] = sc.nextInt(); } int[] dp = new int[1<<n]; Arrays.fill(dp, 1<<29); dp[0] = 0; for(int i=0;i<1<<n;i++) { int discount = 0; for(int j=0;j<n;j++) { if ((i >> j & 1) == 1) { discount += a[j]; } } discount %= 1000; for(int j=0;j<n;j++) { if ((i >> j & 1) == 0) { int to = i|(1<<j); dp[to] = Math.min(dp[to], dp[i] + Math.max(a[j] - discount , 0)); } } } System.out.println(dp[(1<<n)-1]); } }