1.2 Juicy ðŸ¤¤

Score: 15pts

Time Limit: 2.00 sec

Welcome to the world of apples, where n juicy fruits await you, each with its weight known. Your fun challenge is to create two apple groups, but wait, there's a catch â€“ you're aiming for the closest possible total weights in both groups. It's like being a fruit juggler, trying to balance your baskets just right. So, can you split these apples into two teams that feel like they're lifting almost the same weight? The apples are cheering you on to be the ultimate fruity referee in this balancing act!

Constraints

1â‰¤nâ‰¤20

1â‰¤piâ‰¤10^9

1â‰¤piâ‰¤10^9

Input Format

Let's dive into the apple adventure! To begin, the first line of input holds a single integer, n â€“ this represents the count of apples in our fruity tale.

Following that, the next line unfolds with n integers â€“ p1, p2, ..., pn â€“ which reveals the weight of each apple. These weights are the building blocks of our fruity journey.

Following that, the next line unfolds with n integers â€“ p1, p2, ..., pn â€“ which reveals the weight of each apple. These weights are the building blocks of our fruity journey.

Output Format

Time to unveil the result! Your task is to output a single integer. This integer represents the smallest possible difference between the weights of the two groups you've cleverly created. Think of it as the harmonious balance you've achieved in the apple world!

Example 1

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).

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).