Jimin and Hansu's Orchard Split

Time limit2sMemory limit128 MB

Summary

Given up to 50 weighted points on a plane, find a line avoiding all points that splits them into two groups minimizing the difference of their value sums.

Level: Medium7 of 10
Topics: Geometry, Sorting, Prefix sum, Brute force
Solved: No attempts yet

Problem

After Jang Eomji left, Kim Jimin and Im Hansu came to share an orchard. The orchard is represented as a plane, and each fruit tree is represented as one point.

They want to divide the orchard with one straight line. No tree may lie on the line. Trees on one side of the line go to Kim Jimin, and trees on the other side go to Im Hansu.

Each tree has a positive integer value. They want to choose the line so that the sums of the values each person receives are as close as possible.

Given the positions and values of the trees, compute the minimum possible difference between the total value received by Kim Jimin and the total value received by Im Hansu.

Input

The first line contains the number of trees N. N is a natural number between 2 and 50, inclusive.

Each of the next N lines contains a tree's x-coordinate, y-coordinate, and value, in that order. Coordinates are integers between 0 and 1,000, inclusive, and each value is an integer between 1 and 1,000,000, inclusive. No two trees have the same coordinates.

Output

Print the minimum possible difference between the sum of the values of Kim Jimin's trees and the sum of the values of Im Hansu's trees.

Examples6

Example 1
Input
```
2
1 2 10
2 3 20
```
Expected output
```
10
```
Example 2
Input
```
4
0 1 1
1 1 1
2 1 1
3 1 1
```
Expected output
```
0
```
Example 3
Input
```
5
0 1 1
0 2 2
0 3 3
0 4 4
0 5 1000
```
Expected output
```
990
```
Example 4
Input
```
4
0 0 1
0 1 2
1 1 4
1 0 8
```
Expected output
```
1
```

Example 5

Input

Expected output

Example 6
Input
```
3
1 3 1
2 2 1000000
3 1 1
```
Expected output
```
1000000
```