CSES 1623 ↗

Apple Division

Split the apples into two groups minimising the difference of total weights.

0
submissions
—
best score

There are n apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.

Input

The first input line has an integer n: the number of apples.

The next line has n integers p1,p2,…,pn: the weight of each apple.

Output

Print one integer: the minimum difference between the weights of the groups.

Constraints

  • 1≤n≤20
  • 1≤pi≤109

Example

Input:

5
3 2 7 4 1

Output:

1

Explanation: Group 1 has weights 2, 3 and 4 (total weight 9), and group 2 has weights 1 and 7 (total weight 8).

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/AppleDivision/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.