#include <iostream>
#include <random>
#include <algorithm>
#include <numeric>
#include <vector>
#include <chrono>
#include <cstdlib>
#include <iomanip>
#include <iterator>
#include <functional>

enum
{
    kDPLimit = 5000000000, // 5*10^9, dynamic programming
    kHSLimit = 54,         // Horowitz-Sahni
    kKKLimit = 4,          // Karmarkar-Karp
};

using namespace std;
using i64 = int_fast64_t;
using u64 = uint_fast64_t;

class Log
{
public:
    Log(size_t size, i64 max_value, i64 sum, u64 seed, ostream& os)
    : os_(os)
    , start_(chrono::steady_clock::now())
    {
        os_ << "size=" << size
            << " max=" << static_cast<double>(max_value)
            << " sum=" << sum
            << " seed=" << seed
            << '\n';
    }

    template <typename M>
    void operator() (M msg)
    {
        const chrono::duration<double> d = chrono::steady_clock::now() - start_;
        os_ << d.count() << "s:  " << msg << '\n';
    }

    void name(const char* name)
    {
        os_ << name << '\n';
    }

private:
    ostream& os_;
    const chrono::time_point<chrono::steady_clock> start_;
};

template<typename I>
void dp(I b, I e, i64 sum, Log& log)
{
    log.name("dynamic programming");
    vector<char> subset_sums(sum / 2 + 1, false);
    subset_sums[0] = true;

    for_each(b, e, [&](i64 value)
    {
        for (i64 i = sum / 2 - value; i >= 0; --i)
        {
            if (subset_sums[i])
                subset_sums[i + value] = true;
        }
    });

    const auto it = find(subset_sums.rbegin(), subset_sums.rend(), true);
    const auto pos = subset_sums.rend() - it - 1;
    log(sum - 2 * pos);
}

void mergeValue(vector<i64>& to, const vector<i64>& from, i64 value)
{
    to.clear();
    auto original = begin(from);
    auto summed = begin(from);
    const auto last = end(from);

    while (original != last)
    {
        if (summed == last)
        {
            copy(original, last, back_inserter(to));
            return;
        }

        if (*summed + value < *original)
        {
            to.push_back(*summed + value);
            ++summed;
        }
        else
        {
            to.push_back(*original);
            ++original;
        }
    }

    transform(summed, last, back_inserter(to),
              [value](i64 x){return x + value;});
}

template<typename I>
vector<i64> subsetSums(I b, I e)
{
    auto isize = e - b;
    const auto size = 1 << isize;
    vector<i64> subset_sums;
    subset_sums.reserve(size);
    vector<i64> subset_sums2;
    subset_sums2.reserve(size / 2);
    vector<i64>* const ways[2] {&subset_sums, &subset_sums2};
    ways[isize&1]->push_back(0);

    while (isize--)
        mergeValue(*ways[isize&1], *ways[(isize+1)&1], *(b + isize));

    return subset_sums;
}

template<typename I>
void hs(I b, I e, i64 sum, Log& log)
{
    log.name("Horowitz-Sahni");
    const auto middle = (e - b) / 2;
    const vector<i64> first_half = subsetSums(b, b + middle);
    const vector<i64> second_half = subsetSums(b + middle, e);
    const auto target = sum / 2;
    auto result = sum;
    auto it1 = begin(first_half);
    auto it2 = second_half.rbegin();

    while (it1 != end(first_half) && it2 != second_half.rend())
    {
        const auto both = *it1 + *it2;

        if (both > target)
        {
            result = min(result, 2 * both - sum);
            ++it2;
        }
        else
        {
            result = min(result, sum - 2 * both);
            ++it1;
        }

        if (result <= 1)
            break;
    }

    log(result);
}

i64 kkMH(const vector<i64>& values, Log& log)
{
    log.name("Karmarkar-Karp max heap");
    vector<i64> pq(values);
    make_heap(begin(pq), end(pq));

    while (pq.size() > 1)
    {
        auto first = pq[0];
        pop_heap(begin(pq), end(pq));
        pq.pop_back();
        auto second = pq[0];
        pop_heap(begin(pq), end(pq));
        pq[pq.size() - 1] = first - second;
        push_heap(begin(pq), end(pq));
    }

    log(pq[0]);
    return pq[0];
}

template<bool Preprocess = false>
i64 kk(const vector<i64>& values, i64 sum, Log& log)
{
    log.name("Karmarkar-Karp");
    vector<i64> pq(values.size() * 2);
    copy(begin(values), end(values), begin(pq) + values.size());
    sort(begin(pq) + values.size(), end(pq));
    auto first = end(pq);
    auto last = begin(pq) + values.size();

    while (first - last > 1)
    {
        if (Preprocess && first - last <= kHSLimit)
        {
            hs(last, first, sum, log);
            return 0;
        }

        if (Preprocess && static_cast<double>(first - last) * sum <= kDPLimit)
        {
            dp(last, first, sum, log);
            return 0;
        }

        const auto diff = *(first - 1) - *(first - 2);
        sum -= *(first - 2) * 2;
        first -= 2;
        //const auto place = find_if(last, first, [diff](i64 x){return x>=diff;});
        const auto place = lower_bound(last, first, diff);
        --last;
        copy(last + 1, place, last);
        *(place - 1) = diff;
    }

    const auto result = (first - last)? *last: 0;
    log(result);
    return result;
}

// arguments: size, max value, random seed (integers, 0x or 0 prefix allowed)
int main(int argc, char **argv)
{
    size_t size = 10000;
    i64 max_value = 100000000000000ll; // 10^14
    u64 seed  = random_device{}();

    if (argc > 1)
        size = min<u64>(size, strtoull(argv[1], nullptr, 0));

    if (argc > 2)
        max_value = min<u64>(max_value, strtoull(argv[2], nullptr, 0));

    if (argc > 3)
        seed = strtoull(argv[3], nullptr, 0);

    mt19937_64 rng(seed);
    uniform_int_distribution<i64> ud(1, max_value);
    auto gen = bind(ud, rng);
    vector<i64> values(size);
    generate_n(begin(values), size, gen);
    const auto sum = accumulate(begin(values), end(values), 0ll);
    Log log(size, max_value, sum, seed, cout);

    if (kk(values, sum, log) > 1 && size > kKKLimit)
        kk<true>(values, sum, log);
}