가장 균형 잡힌 배심원단

배심원 재판을 하는 여러 나라에서는 유권자 명부에서 무작위로 뽑은 후보 명단에서 배심원을 고른다. 검사와 변호인은 자기 쪽에 불리하다고 판단한 후보를 거부할 권리가 있다. 그래서 최종 배심원단에는 대체로 무난한 사람만 남고, 견해가 뚜렷해서 오히려 논의에 보탬이 될 만한 후보가 바로 그 이유로 걸러진다.

더 나은 방법은 후보마다 검사 측 수치와 변호인 측 수치를 매기는 것이다. 후보 한 명의 균형은 두 수치의 차이고, 가치는 두 수치의 합이다. 배심원단의 균형은 뽑은 후보의 검사 측 수치 합과 변호인 측 수치 합의 차를 절댓값으로 잰 값이고, 배심원단의 가치는 뽑은 후보의 수치를 모두 더한 값이다. 균형이 가장 작은 배심원단을 고르고, 균형이 같은 배심원단이 여럿이면 가치가 가장 큰 것을 고른다.

규칙을 작은 예로 보자. 후보 (20, 1), (1, 20), (10, 9), (10, 9) 네 명에서 두 명을 고른다면 앞의 두 명은 균형이 0이고 뒤의 두 명은 균형이 2다. 마지막 후보가 (9, 10)이었다면 뒤의 두 명도 균형이 0이 되지만 가치가 38로 앞의 두 명의 42보다 작으므로 여전히 앞의 두 명을 고른다.

후보 명단과 뽑을 배심원 수가 주어졌을 때 가장 균형 잡힌 배심원단을 찾는 프로그램을 작성하시오. 균형과 가치가 모두 같은 배심원단이 여럿이면 번호를 오름차순으로 나열한 목록이 사전순으로 가장 앞서는 것을 고른다. 두 목록은 앞에서부터 견주어 처음으로 달라지는 자리의 번호가 더 작은 쪽이 앞선다.

입력은 후보 명단 여러 개로 이루어진다. 각 명단은 뽑을 배심원 수 $k$ ($5 \le k \le 20$)가 홀로 적힌 줄로 시작한다. 그 뒤에는 후보 한 명당 한 줄씩 최대 100줄이 이어지고, 각 줄에는 그 후보의 검사 측 수치와 변호인 측 수치가 정수 두 개로 주어진다. 두 수치는 모두 1 이상 20 이하다. 후보에게는 나온 순서대로 1번부터 번호를 붙이며, 이 번호로 후보를 가리킨다. 한 명단에는 후보가 $k$명 이상 있다. 명단은 0이 두 개 적힌 줄로 끝난다. 입력 전체는 0이 하나만 적힌 줄로 끝난다.

후보 명단마다 두 줄을 출력한다. 첫 줄에는 배심원단 번호와 균형, 가치를 Jury i: balance b, value v 형식으로 적는다. 배심원단 번호는 1부터 시작해 명단마다 1씩 늘어난다. 둘째 줄에는 뽑은 배심원 $k$명의 번호를 오름차순으로, 공백 하나로 구분해 적는다. 조건을 만족하는 배심원단이 여럿이면 번호 목록이 사전순으로 가장 앞서는 것을 출력한다. 배심원단과 배심원단 사이에는 빈 줄을 하나 넣고, 마지막 배심원단 뒤에는 빈 줄을 넣지 않는다.