//Generated at 2020-08-11 18:50:36 UTC+8
//Created by Alphagocc
#if __cplusplus < 201103L
#    define ___TR1(x) <tr1/x>
#else
#    define ___TR1(x) <x>
#endif
#ifndef _GLIBCXX_NO_ASSERT
#    include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <climits>
#include <clocale>
#include <cmath>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include ___TR1(cstdbool)
#include ___TR1(cstdint)
#include ___TR1(ctgmath)
#include ___TR1(cfenv)
#include ___TR1(cinttypes)
#if __cplusplus >= 201103L
#    include <ccomplex>
#else
#    include <tr1/complex>
#endif
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include ___TR1(array)
#include ___TR1(random)
#include ___TR1(tuple)
#include ___TR1(unordered_map)
#include ___TR1(unordered_set)
#if __cplusplus >= 201103L
#    include <atomic>
#    include <chrono>
#    include <condition_variable>
#    include <forward_list>
#    include <future>
#    include <initializer_list>
#    include <mutex>
#    include <ratio>
#    include <regex>
#    include <scoped_allocator>
#    include <system_error>
#    include <thread>
#    include <type_traits>
#    include <typeindex>
#endif
#ifdef USE_PBDS
#    include <ext/pb_ds/assoc_container.hpp>
#    include <ext/pb_ds/priority_queue.hpp>
#endif
#define FORCE_INLINE __inline__ __attribute__((always_inline))
class IO
{
    static const int bufSize = 1 << 18;

    char inBuf[bufSize], outBuf[bufSize];
    char *ip1 = inBuf, *ip2 = inBuf;

    int goodReadBit = 1, op1 = -1, op2 = bufSize - 1;

    FORCE_INLINE int gc()
    {
        return ip1 == ip2
                && (ip2 = (ip1 = inBuf) + fread(inBuf, 1, bufSize, stdin),
                    ip1 == ip2)
            ? EOF
            : *ip1++;
    }

    template <typename T> FORCE_INLINE void __RI(T &x)
    {
        int ch = gc(), neg = 1;
        x = 0;
        for (; !(isdigit(ch) || ch == '-'); ch = gc())
            ;
        if (ch == EOF) {
            goodReadBit = 0;
            return;
        }
        if (ch == '-') neg = -1, ch = gc();
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - 48) * neg;
    }
    template <typename T> FORCE_INLINE void __RC(T &x)
    {
        int ch;
        while (isspace(ch = gc()))
            ;
        if (ch == EOF) {
            goodReadBit = 0;
            return;
        }
        x = ch;
    }
    FORCE_INLINE void __RS(std::string &x)
    {
        char ch;
        x.clear();
        for (ch = gc(); isspace(ch); ch = gc())
            ;
        if (ch == EOF) {
            goodReadBit = 0;
            return;
        }
        for (; !isspace(ch); ch = gc()) x.push_back(ch);
    }

public:
    // input
    // char types
    FORCE_INLINE IO &R(char &x)
    {
        __RC(x);
        return (*this);
    }
    FORCE_INLINE IO &R(unsigned char &x)
    {
        __RC(x);
        return (*this);
    }
    // string types
    FORCE_INLINE IO &R(std::string &x)
    {
        __RS(x);
        return (*this);
    }
    // easy STL
    template <typename T1, typename T2> FORCE_INLINE IO &R(std::pair<T1, T2> &x)
    {
        R(x.first);
        R(x.second);
        return (*this);
    }
    template <typename T> FORCE_INLINE IO &R(std::vector<T> &x)
    {
        for (typename std::vector<T>::iterator it = x.begin(); it != x.end();
             ++it)
            R(*it);
        return (*this);
    }
    template <typename T, typename... Args> FORCE_INLINE IO &RA(T *a, int n)
    {
        for (int i = 0; i < n; ++i) R(a[i]);
        return (*this);
    }
#if __cplusplus >= 201103L
    template <typename T, typename... Args>
    FORCE_INLINE IO &R(T &x, Args &... args)
    {
        R(x), R(args...);
        return (*this);
    }
    template <typename T, typename... Args>
    FORCE_INLINE IO &RA(T *a, int n, Args... args)
    {
        for (int i = 0; i < n; ++i) RA(a[i], args...);
        return (*this);
    }
    template <typename T> FORCE_INLINE IO &R(T &x)
    {
        static_assert(std::is_integral<T>::value, "Unsupported types");
        if (std::is_integral<T>::value) __RI(x);
        return (*this);
    }
#else
    template <typename T> FORCE_INLINE IO &R(T &x)
    {
        if (std::numeric_limits<T>::is_integer)
            __RI(x);
        else
            throw std::invalid_argument("Unsupported types");
        return (*this);
    }
#endif

private:
    // output
    char space;
    FORCE_INLINE void pc(const char &x)
    {
        if (op1 == op2) flush();
        outBuf[++op1] = x;
    }
    template <typename T> FORCE_INLINE void __WI(T x)
    {
        static char buf[64];
        static int len = -1;
        if (x >= 0) {
            do {
                buf[++len] = x % 10 + 48, x /= 10;
            } while (x);
        } else {
            pc('-');
            do {
                buf[++len] = -(x % 10) + 48, x /= 10;
            } while (x);
        }
        while (len >= 0) { pc(buf[len]), --len; }
    }

public:
    FORCE_INLINE void flush() { fwrite(outBuf, 1, op1 + 1, stdout), op1 = -1; }
    // char types
    FORCE_INLINE IO &W(const char &x)
    {
        pc(x);
        return (*this);
    }
    // string types
    FORCE_INLINE IO &W(const char *x)
    {
        while (*x != '\0') pc(*(x++));
        return (*this);
    }
    FORCE_INLINE IO &W(const std::string &x)
    {
        W(x.c_str());
        return (*this);
    }
    // easy stl
    template <typename T> FORCE_INLINE IO &W(const std::vector<T> &x)
    {
        for (typename std::vector<T>::const_iterator it = x.begin();
             it != x.end(); it++)
            WS(*it);
        WL();
        return (*this);
    }
    template <typename T1, typename T2> FORCE_INLINE IO &W(std::pair<T1, T2> &x)
    {
        WS(x.first);
        W(x.second);
        return (*this);
    }
    FORCE_INLINE IO &WL()
    {
        W('\n');
        return (*this);
    }
    template <typename T> FORCE_INLINE IO &WL(const T &x)
    {
        W(x), W('\n');
        return (*this);
    }
    FORCE_INLINE IO &WS()
    {
        W(' ');
        return (*this);
    }
    template <typename T> FORCE_INLINE IO &WS(const T &x)
    {
        W(x), W(space);
        return (*this);
    }
    template <typename T> FORCE_INLINE IO &WA(T *a, int n)
    {
        for (int i = 0; i < n; i++) WS(a[i]);
        WL();
        return (*this);
    }
#if __cplusplus >= 201103L
    template <typename T, typename... Args>
    FORCE_INLINE IO &W(const T &x, const Args &... args)
    {
        W(x), W(space), W(args...);
        return (*this);
    }
    template <typename... Args> FORCE_INLINE IO &WL(const Args &... args)
    {
        W(args...), W('\n');
        return (*this);
    }
    template <typename T, typename... Args>
    FORCE_INLINE IO &WA(T *a, int n, Args... args)
    {
        for (int i = 0; i < n; i++) WA(a[i], args...);
        return (*this);
    }
    template <typename T> FORCE_INLINE IO &W(const T &x)
    {
        static_assert(std::is_integral<T>::value, "Unsupported types");
        if (std::is_integral<T>::value) __WI(x);
        return (*this);
    }
#else
    template <typename T> FORCE_INLINE IO &W(const T &x)
    {
        if (std::numeric_limits<T>::is_integer)
            __WI(x);
        else
            throw std::invalid_argument("Unsupported types");
        return (*this);
    }
#endif
    template <typename T> FORCE_INLINE IO &operator>>(T &x)
    {
        R(x);
        return (*this);
    }
    template <typename T> FORCE_INLINE IO &operator<<(const T &x)
    {
        W(x);
        return (*this);
    }
    IO() { space = ' '; }
} io;
namespace Alphagocc
{
#if __cplusplus >= 201103L
decltype(std::chrono::high_resolution_clock::now()) tStart;
};
void TimeBegin()
{
    Alphagocc::tStart = std::chrono::high_resolution_clock::now();
}
long long TimeEnd()
{
    return (std::chrono::high_resolution_clock::now() - Alphagocc::tStart)
        .count();
#endif
} // namespace Alphagocc
#if __cplusplus >= 201103L
std::random_device randomDevice;
std::mt19937 randomGenerator(randomDevice());
#else
std::tr1::random_device randomDevice;
std::tr1::mt19937 randomGenerator(randomDevice());
#endif
using namespace std;
#if __cplusplus < 201103L
using namespace tr1;
#endif
void EXIT(int code) { io.flush(), exit(code); }
#define REP(i, x, y) for (int i = x; i < y; i++)
const int8_t INFC = 0x3f;
const int16_t INFS = 0x3f3f;
const int32_t INF = 0x3f3f3f3f;
const int64_t INFL = 0x3f3f3f3f3f3f3f3fLL;

bitset<int(5e6)> dp;
int main()
{
    int n;
    io >> n;
    vector<int> a(n);
    io >> a;
    int sum = 0;
    dp.set(0);
    for (auto i : a) {
        dp |= dp << i;
        sum += i;
    }
    for (int i = (sum + 1) / 2; i <= sum; i++)
        if (dp.test(i)) {
            io.WL(i);
            break;
        }
    EXIT(0);
}

Measured memory_bytes: 4268