공평한 분할

N개의 보석이 2차원 평면 위에 있다. 각 보석은 (x, y) 좌표에 위치하며 가치 w를 가진다.

평면 위에 하나의 직선을 그어 보석을 두 그룹으로 나누려고 한다. 단, 직선 위에 보석이 있어서는 안 된다.

두 그룹의 보석 가치 합의 차이를 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 보석의 수 N이 주어진다. (2 <= N <= 50)
둘째 줄부터 N개의 줄에 각 보석의 x, y 좌표와 가치 w가 공백으로 구분되어 주어진다. (0 <= x, y <= 1,000, 1 <= w <= 1,000,000)

같은 좌표에 두 보석이 있는 경우는 없다.

출력

두 그룹의 가치 합 차이의 최솟값을 출력한다.

입출력 예시

입력 1

2
1 2 10
2 3 20

출력 1

10

입력 2

4
0 1 1
1 1 1
2 1 1
3 1 1

출력 2

0