import java.util.*;

class Solution {

    private int[] absA;
    private int sum;
    private Map<Integer, Integer> countMap = new HashMap<>();
    private int[] subset;

    public int solution(int[] A) {
        this.absA = getAbs(A);
        this.sum = getSum(absA);
        this.countMap = getCountMap(absA);
        this.subset = new int[Math.max(sum, 1)];

        Arrays.fill(subset, -1);
        subset[0] = 0;

        for (int key : countMap.keySet()) {
            for (int i=0; i<sum/2+1; i++) {
                if (subset[i] >= 0) {
                    subset[i] = countMap.get(key);
                } else if (i >= key && subset[i - key] > 0) {
                    subset[i] = subset[i - key] - 1;
                }
            }
        }

        int res = sum;
        for (int i=0; i<sum/2+1; i++) {
            if (subset[i] >= 0) {
                res = Math.min(res, sum - i * 2);
            }
        }

        return res;
    }

    private int[] getAbs(int[] A) {
        int[] absA = new int[A.length];
        for (int i=0; i<A.length; i++) {
            absA[i] = Math.abs(A[i]);
        }

        return absA;
    }

    private int getSum(int[] A) {
        int sum = 0;
        for (int i=0; i<A.length; i++) {
            sum += A[i];
        }

        return sum;
    }

    private Map<Integer, Integer> getCountMap(int[] A) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int i=0; i<A.length; i++) {
            countMap.put(A[i], countMap.getOrDefault(A[i], 0) + 1);
        }

        return countMap;
    }
}