시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB118352124.706%

문제

장엄지는 과일밭을 소유하고 있었다. 하지만 장엄지가 어디론가 떠나는 바람에 김지민과 임한수가 그 밭을 가지게 되었다. 과일밭은 평면으로 표현되며 과일나무는 점 하나로 표현된다.

김지민과 임한수는 과일밭을 직선을 이용해서 나누려고 한다. 단, 직선 위에는 나무가 있으면 안 된다. 이렇게 되면 김지민은 과일밭의 한 쪽을 가지게 되고, 임한수는 다른 한 쪽을 가지게 된다.

두 사람은 모두 과일 나무를 이용해서 이윤을 창출하려고 하기 때문에, 모든 나무에 각각의 가치를 매겼다. 공평하게 밭을 나누기 위해서 김지민이 가지고 있는 나무의 가치의 합과 임한수 것의 차이를 최소로 하려고 한다.

나무의 위치가 주어졌을 때, 김지민과 임한수가 가지고 있는 나무의 가치 차이의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 개수 N이 주어진다. N은 2보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 나무의 x, y좌표와 가치가 주어진다. 좌표는 1,000보다 작거나 같은 음이 아닌 정수이고, 가치는 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

예제 입력 3

5
0 1 1
0 2 2
0 3 3
0 4 4
0 5 1000

예제 출력 3

990

예제 입력 4

4
0 0 1
0 1 2
1 1 4
1 0 8

예제 출력 4

1

예제 입력 5

8
4 1 4
2 2 5
4 4 2
2 3 6
3 3 7
6 2 4
3 4 2
5 5 4

예제 출력 5

2

예제 입력 6

3
1 3 1
2 2 1000000
3 1 1

예제 출력 6

1000000

출처