공정한 배심원단

브루토피아에서는 법정 판결을 일반 시민으로 구성된 배심원단이 내린다. 재판을 시작하기 전에 후보자 명단에서 배심원단을 선정해야 한다.

명단에 있는 각 후보자 $i$에 대해 검찰은 값 $p_i$를, 변호인은 값 $d_i$를 매기며, 두 값 모두 $0$ 이상 $20$ 이하의 정수이다. 값이 클수록 해당 측이 그 후보자를 더 적합하다고 평가한 것이다.

정확히 $m$명의 후보자로 이루어진 배심원단 $J$를 선택해야 한다. 선택한 배심원단 $J$에 대해 다음과 같이 정의한다.

$D(J) = \sum_{k \in J} d_k \qquad P(J) = \sum_{k \in J} p_k$

즉 $D(J)$는 변호인 측 값의 합, $P(J)$는 검찰 측 값의 합이다.

재판이 공정하려면 배심원단이 어느 한쪽에도 치우치지 않아야 하므로 $|D(J) - P(J)|$가 가능한 한 작아야 한다. 이 최소 차이를 달성하는 모든 배심원단 중에서는 양측 모두에게 가치가 큰 배심원단이 좋으므로 $D(J) + P(J)$가 가능한 한 커야 한다.

후보자 명단이 주어질 때 이 두 최적 값을 구하라.

입력은 여러 개의 배심원단 선정 라운드로 이루어진다.

각 라운드는 두 정수 $n$과 $m$이 적힌 줄로 시작한다. $n$은 후보자 수, $m$은 선정할 배심원 수이며 $1 \le n \le 200$, $1 \le m \le 20$, $m \le n$을 만족한다.

이어지는 $n$개의 줄에는 각각 두 정수 $p_i$와 $d_i$ ($0 \le p_i, d_i \le 20$)가 있으며, 이는 후보자 $i$의 검찰 측 값과 변호인 측 값이다.

라운드 사이는 빈 줄로 구분될 수 있다. 입력은 0 0이 적힌 라운드로 끝나며, 이 라운드는 처리하지 않는다.

각 라운드마다 세 줄을 출력한다.

첫 줄은 Jury #k이며 k는 $1$부터 시작하는 라운드 번호이다. 둘째 줄은 달성 가능한 최소 차이를 출력한다. 셋째 줄은 그 최소 차이를 달성하는 배심원단 중 최대 합을 출력한다.

두 값은 정확히 다음 형식으로 출력한다.

Jury #k
Minimum difference |D(J) - P(J)| is X
Maximum total D(J) + P(J) is Y

여기서 X는 |D(J) - P(J)|의 최솟값이고, Y는 그 최소 차이를 달성하는 모든 배심원단에 대한 D(J) + P(J)의 최댓값이다.

각 라운드 뒤에는 빈 줄을 하나 출력한다.

$m \le n$이므로 정확히 $m$명으로 이루어진 배심원단은 항상 존재한다. 가능한 모든 $\binom{n}{m}$개의 배심원단을 전부 확인하는 완전 탐색은 주어진 제한에서 너무 느리다. $D(J) - P(J)$가 가질 수 있는 값에 대한 동적 계획법과 같은 효율적인 방법이 필요하다.