배심원 절충

머나먼 나라 프로브니아(Frobnia)에서는 법원의 판결을 일반 시민으로 구성된 배심원단이 결정한다. 재판이 시작될 때마다 다음과 같은 방식으로 배심원단을 뽑는다. 먼저 시민들 가운데 무작위로 후보 풀을 구성한다. 이 풀의 각 후보에 대해 변호인 측과 검사 측이 각각 그 후보를 얼마나 선호하는지를 $0$부터 $20$까지의 점수로 매긴다. $0$은 완전한 거부를, $20$은 배심원으로 가장 이상적이라고 보는 것을 뜻한다.

판사는 이 두 점수를 바탕으로 배심원단을 선정한다. 공정한 재판을 위해 배심원단이 변호인 측이나 검사 측 어느 한쪽으로도 치우치지 않고 최대한 균형을 이루어, 양측 모두가 받아들일 수 있어야 한다.

이를 정확히 정의하면 다음과 같다. $n$명의 후보로 이루어진 풀이 주어지고, 각 후보 $i$에 대해 검사 측 점수 $p_i$와 변호인 측 점수 $d_i$가 주어진다. 이 중에서 정확히 $m$명의 배심원을 선택해야 한다. $m$개의 원소를 갖는 부분집합 $J \subseteq \{1, \dots, n\}$에 대해 $D(J) = \sum_{k \in J} d_k$, $P(J) = \sum_{k \in J} p_k$ 는 각각 이 배심원단의 변호인 측 총점과 검사 측 총점이다.

최적의 배심원단은 다음 규칙을 순서대로 적용하여 정한다.

1. 불균형 $|D(J) - P(J)|$ 가 가능한 한 작아야 한다.
2. 그 최소 불균형을 갖는 배심원단들 중에서 합 $D(J) + P(J)$ 가 가능한 한 커야 한다. 그래야 양측 모두에게 가치가 큰 배심원단이 된다.
3. 그래도 여러 배심원단이 동점이면, 후보 번호들을 오름차순으로 나열한 목록이 "유사 알파벳" 순서로 가장 앞서는 배심원단을 택한다. 즉 정렬된 후보 목록을 마치 번호가 글자인 것처럼 비교한다. 예를 들어 $1,5,6,9$ 는 $1 < 2$ 이므로 $2,3,4,5$ 보다 앞서고, $1,2,3,5,9$ 는 $5 < 6$ 이므로 $1,2,3,6,9$ 보다 앞선다.

이 세 규칙을 함께 적용하면 항상 정확히 하나의 배심원단이 결정된다. 이 선정 과정을 수행하는 프로그램을 작성하라.

입력은 여러 개의 배심원 선정 라운드로 이루어진다. 각 라운드는 두 정수 $n$ 과 $m$ 이 담긴 줄로 시작한다. $n$ 은 후보 수, $m$ 은 배심원 수이며 $1 \le n \le 200$, $1 \le m \le 20$, 그리고 $m \le n$ 을 만족한다. 이어지는 $n$ 개의 줄에는 각각 두 정수 $p_i$ 와 $d_i$ (후보 $i$ 에 대한 검사 측 점수와 변호인 측 점수)가 주어지며 $0 \le p_i, d_i \le 20$ 이다. 라운드 사이는 빈 줄로 구분될 수 있다.

입력의 마지막은 첫 줄이 0 0 인 라운드로 끝나며, 이 종료 라운드는 처리하지 않는다.

각 라운드마다 Jury #r 이라는 줄을 출력한다. 여기서 $r$ 은 라운드 번호($1, 2, \dots$)이다.

다음 줄에는 검사 측 총점과 변호인 측 총점을 정확히 다음 형식으로(검사 측을 먼저, 변호인 측을 나중에) 출력한다.

Best jury has value <P(J)> for prosecution and value <D(J)> for defence:

그 다음 줄에는 선택된 $m$ 명의 후보 번호를 오름차순으로 출력하되, 각 번호 앞에 공백 하나를 붙인다.

연속한 라운드 사이에는 빈 줄을 하나 출력한다. 첫 라운드 앞과 마지막 라운드 뒤에는 빈 줄이 없다.