# -*- coding: utf-8 -*- 
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/9/2
# @File : D - Cooking（DP子集和问题）.py
# https://atcoder.jp/contests/abc204/tasks/abc204_d

#一层循环一维矩阵做法（bitset）位运算，并行更新
def dp_solve():
    bitset = 1
    total = 0
    for i in range(n + 1):
        bitset |= bitset << rate[i]
        total += rate[i]

    part = total // 2
    if (total % 2 == 1):
        part = part + 1

    dp = bin(bitset)[2:]

    for j in range(part, total + 1):
        if (dp[j] == '1'):
            return j
"""
j位对应j-rate[i]位，rate[i]对应第0位（右端点），所以左移rate[i]，每次更新一批的j
小于rate[i]的部分直接不变即可，因为左移补零，与0进行或运算结果保持不变
左移后突出的部分不用管，直接丢掉即可，因为这一部分需要更新或者保持不变，每次需要更新S - rate[i]个

01串数组其实是中点（S/2）对称的，因为j能组成 S-j也一定能
所以可以不用反转01串数组


三种方法都是直接求t2（大的那个），求t1的话需要输出S-t1=t2
"""

#二层循环一维矩阵做法
def dp_solve1():
    dp = [True] * (total + 1)
    for i in range(1, total + 1):
        dp[i] = False
    for i in range(1, n + 1):
        for j in range(total, rate[i] - 1, -1):#一维数组的话必须倒序
            dp[j] = dp[j] or dp[j - rate[i]]

    #填完表再搜索
    for j in range(part, total + 1):
        if (dp[j] == True):
            return j

#二层喜欢二维矩阵做法
def dp_solve2():
    dp = [[True]*(total+1) for i in range(n+1)]
    for i in range(1,total+1):
        dp[0][i] = False#初始化
    for i in range(1,n+1):
        for j in range(1,total+1):#都是从1开始
            if(j < rate[i]):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j] or dp[i-1][j-rate[i]]
            if(i==n and j >= part and dp[i][j]==True):# 这里的i==n 不能删去（*）
                return j
"""
子集和问题，时间复杂度O（N*Sum（arr））

思考思路：两个烤炉，加起来的和肯定等于数组总和，选一些数在烤炉A 另外的全部都在烤炉B 
要求两个烤炉中较大值的最小值，即全部都要煮好的最小值
假设数组总和为S
因此两个烤炉中的较大值一定在S/2到S之间，因为两个烤炉地位相等可以对调，设为M
现在要找到最小值的M

方法：DP动态规划法

怎么找呢，就是子集和问题，一个数组内选若干个数可以加起来为M，所以在dp过程中遇到大于等于S/2的第一个为”真“的M就是最小值的M

dp[i][j]代表前i个的元素中选择若干个能否组成和为j，能为True 不能为False

初始化的dp数组框架：
1 0 0 0 0 
1
1
1
如果j < rate[i] 就代表i不能被选中，那就只能dp[i][j] = dp[i-1][j]
如果j >= rate[i] ，就代表可以选和可以不选 ，两种选择中有一个为真（能组成），dp[i][j]就为真 ， dp[i][j] = dp[i-1][j] or dp[i-1][j-rate[i]]


（*）会误以为既然前面的都能选出来，后面的包含前面的肯定也可以，所以i不需要到达n，这种想法是错误的 
    因为你的j是未知的是要求的数，你不能保证i<n时的j>=part的第一个j就是那个准确的i==n时j >= part的那个j，这是并不确定的，
    这是很有可能不一样的。所以一定要有全部数（i==n）这个条件才行，比如第一个case就是可以证明这一点。
"""
if __name__ == '__main__':
    n = int(input())
    rate = [int(i) for i in input().split()]
    rate = [0]+rate
    total = sum(rate)
    part = total//2
    if(total%2 == 1):
        part = part + 1#如果是除不尽，就是从大于S/2的第一个整数开始，也就是total//2+1（total为奇数）
    ans = dp_solve()
    print(ans)