생산 라인의 공통 보정값

문제

한 공장에서는 두 공급 장치가 함께 작동하는 생산 라인을 시험하고 있다. 첫 번째 공급 장치에는 정수 보정값 X를, 두 번째 공급 장치에는 정수 보정값 Y를 설정한다. 두 보정값은 각각 0 이상 K 이하로 정할 수 있다. 두 장치가 같은 보정값을 사용해도 되며, 어느 한쪽 또는 양쪽을 모두 0으로 설정해도 된다. 시험 기록은 N개이다. 각 기록에는 첫 번째 장치의 작동 횟수 A, 두 번째 장치의 작동 횟수 B, 그리고 목표 공급량 T가 적혀 있다. 보정값을 X와 Y로 정했을 때 해당 기록의 예상 공급량은 A×X+B×Y이다. 예상 공급량이 목표보다 많거나 적은 정도를 모두 오차로 계산한다. 따라서 해당 기록의 오차는 A×X+B×Y와 T의 차이의 절댓값이다. 예상 공급량이 목표와 정확히 같으면 그 기록의 오차는 0이다. 공장은 하나의 설정으로 여러 작업을 처리하므로 시험 기록마다 보정값을 따로 정할 수 없다. 모든 기록에 같은 X와 Y를 적용해야 한다. 전체 오차는 각 기록의 오차를 모두 더한 값이다. 내용이 완전히 같은 기록이 여러 번 주어져도 각각 별도의 시험이므로, 입력에 나타난 횟수만큼 전체 오차에 더한다. 어느 한 장치의 작동 횟수가 0인 기록도 유효하며, 두 장치가 모두 작동하지 않은 기록도 있을 수 있다. 담당자는 전체 오차가 가장 작은 설정을 찾으려 한다. 전체 오차가 같은 설정이 여러 개라면 X가 가장 작은 설정을 선택한다. 그중에서도 여러 개가 남으면 Y가 가장 작은 설정을 선택한다. 전체 오차를 0으로 만들 수 없어도 가장 작은 오차를 만드는 설정을 출력해야 한다. 허용되는 보정값의 범위에는 항상 0이 포함되므로 선택 가능한 설정은 반드시 존재한다. 선택한 두 보정값과 그 설정의 전체 오차를 구한다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1 ≤ N ≤ 200이며 0 ≤ K ≤ 30이다.
다음 N개 줄에 각 시험 기록의 정수 A, B, T가 공백으로 주어진다. 0 ≤ A, B ≤ 100이며 0 ≤ T ≤ 10,000이다. 기록의 순서는 결과에 영향을 주지 않는다.

출력

선택한 X, 선택한 Y, 전체 오차를 순서대로 공백으로 구분하여 한 줄에 출력한다. 전체 오차가 같으면 X가 작은 설정을, X도 같으면 Y가 작은 설정을 출력한다.

2 2
1 0 2
0 1 1

2 1 0

1 1
2 2 3

0 1 1

2 0
0 0 7
3 4 5

0 0 12

출처: Devin.KR 자체 제작