// Arup Guha
// 3/1/2014
// Solution to 2014 Mercer Contest Problem 8: Queen Dido's New Challenge - written in contest

import java.util.*;

public class prob8 {

	public static void main(String[] args) {

		// Go through each case.
		Scanner stdin = new Scanner(System.in);
		while (stdin.hasNext()) {

			// Read in data, keeping track of sum.
			int n = stdin.nextInt();
			int[] vals = new int[n];
			int sum = 0;
			for (int i=0; i<n; i++) {
				vals[i] = stdin.nextInt();
				sum += vals[i];
			}

			// Run subset sum DP.
			boolean[] arr = new boolean[sum+1];
			arr[0] = true;
			for (int i=0; i<n; i++) {
				for (int j=sum; j>=vals[i]; j--)
					if (arr[j-vals[i]])
						arr[j] = true;
			}

			// Look for closest valid sum to half of total and answer with corresponding area.
			long ans = 0;
			for (int i=sum/2; i<=sum; i++) {
				if (arr[i]) {
					ans = (((long)i)*(sum-i)+1)/2L;
					break;
				}
			}
			System.out.println(ans);
		}
	}
}