Jimin and Hansu's Orchard Split

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.

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.

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.