시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 28 7 5 20.833%

문제

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

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

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

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

입력

첫째 줄에 나무의 개수 N이 주어진다. 100개보다 작거나 같은 자연수이고 1은 아니다. 둘째 줄부터 N개의 줄에 나무의 좌표와 가치가 주어진다. 좌표는 중복되지 않으며, 좌표는 1,000보다 작거나 같은 음이 아닌 정수이고, 가치는 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 김지민이 가지고 있는 나무의 가치의 합과 임한수가 가지고 있는 나무의 가치의 합의 차이의 최솟값을 출력한다.

예제 입력

2
1 2 10
2 3 20

예제 출력

10

힌트

출처