# Divide the weights

Given

`n`

weights

, you are asked to split those weights into 2 groups so that the difference between those weights is minimal. Input

The first line of the input contains a single integer

`n`

(1 ≤ n ≤ 20).The next line contains

`n`

space-separated integers

(1 ≤ ≤ ). Output

The program should print the minimal possible difference between the two groups.

Examples

Input | Output |

3
3 2 1 | 0 |

5
1 2 3 4 7 | 1 |

Explanation

- First group → 3, second group → 1 + 2 = 3

- First group → 1 + 7 = 8, second group → 2 + 3 + 4 = 9

## Hint

You can try to split the weights in all the possible ways and calculate the minimum possible difference.

#### Constraints

Time limit: 0.2 seconds

Memory limit: 512 MB

Output limit: 1 MB