Problem: You are given N integers A_1, A_2, ..., A_N.

Consider the sums of all non-empty subsequences of A. There are 2^N - 1 such sums, an odd number.

Let the list of these sums in non-decreasing order be S_1, S_2, ..., S_{2^N - 1}.

Find the median of this list, S_{2^{N-1}}.

Constraints

* 1 \leq N \leq 2000
* 1 \leq A_i \leq 2000
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 ... A_N


Output

Print the median of the sorted list of the sums of all non-empty subsequences of A.

Examples

Input

3
1 2 1


Output

2


Input

1
58


Output

58

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Main {

	static class BitsetLong {

		static final int LOG = 6;
		static final int SIZE = 1 << LOG;
		static final int MASK = SIZE - 1;

		private long[] data;
		
		int n;

		public BitsetLong(int n) {
			this.n = n;
			data = new long[(n >> LOG) + 2];
		}

		void set(int i) {
			data[i >> LOG] |= 1L << (i & MASK);
		}

		void unset(int i) {
			data[i >> LOG] &= ~(1L << (i & MASK));
		}

		void flip(int i) {
			data[i >> LOG] ^= 1L << (i & MASK);
		}

		int get(int i) {
			return (int) ((data[i >> LOG] >>> (i & MASK)) & 1);
		}

		/**
		 * pads with zeroes if end of word is outside of range
		 */
		long getWord(int i) {
			
			if (i <= -SIZE || i >= n) {
				return 0;
			}
			
			int rem = i & MASK;
			int idx = i >> LOG;
			
			if (i < 0) {
				return (data[idx + 1] & ((1L << rem) - 1)) << (SIZE - rem);
			}

			if (rem == 0) {
				return data[idx];
			}

			long head = data[idx] >>> rem;
			long tail = data[idx + 1] & ((1L << rem) - 1);

			return head | (tail << (SIZE - rem));
		}
	}

	int solve(int[] a) {
		int sum = 0;
		
		BitsetLong cur = new BitsetLong(sum + 1);
		cur.set(0);
		
		for (int x : a) {
			sum += x;
			
			BitsetLong now = new BitsetLong(sum + 1);
			for (int i = 0; i < now.data.length; i++) {
				now.data[i] = cur.getWord(i << BitsetLong.LOG) | cur.getWord((i << BitsetLong.LOG) - x);  
			}
			cur = now;
		}
		
		int seek = (sum + 1) / 2;
		while (cur.get(seek) == 0) {
			seek++;
		}
		return seek;
	}

	void submit() {
		int n = nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}

		out.println(solve(a));
	}

	void preCalc() {

	}

	void stress() {

	}

	void test() {
		int n = 2000;
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = n;
		}
		out.println(solve(a));
	}

	Main() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		preCalc();
		submit();
		// stress();
//		 test();
		out.close();
	}

	static final Random rng = new Random();

	static int rand(int l, int r) {
		return l + rng.nextInt(r - l + 1);
	}

	public static void main(String[] args) throws IOException {
		new Main();
	}

	BufferedReader br;
	PrintWriter out;
	StringTokenizer st;

	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return st.nextToken();
	}

	String nextString() {
		try {
			return br.readLine();
		} catch (IOException e) {
			throw new RuntimeException(e);
		}
	}

	int nextInt() {
		return Integer.parseInt(nextToken());
	}

	long nextLong() {
		return Long.parseLong(nextToken());
	}

	double nextDouble() {
		return Double.parseDouble(nextToken());
	}
}