Jury Compromise

In the far-away country of Frobnia, court verdicts are decided by a jury drawn from the general public. Whenever a trial begins, a jury must be selected as follows. First, a pool of people is drawn at random. For each person in the pool the defence and the prosecution each assign a grade from $0$ to $20$ that expresses how strongly they favour that person: $0$ means total rejection, while $20$ means the person is considered ideal for the jury.

Using these two grades, the judge picks the jury. To keep the trial fair, the jury's overall leaning toward the defence or the prosecution should be as balanced as possible, so the jury must be satisfactory to both sides.

Formally, you are given a pool of $n$ candidates. For each candidate $i$ you are given the prosecution's grade $p_i$ and the defence's grade $d_i$. You must choose a jury of exactly $m$ people. For a subset $J \subseteq \{1, \dots, n\}$ with $m$ elements, let $D(J) = \sum_{k \in J} d_k$ and $P(J) = \sum_{k \in J} p_k$ be the jury's total value for the defence and for the prosecution.

An optimal jury is determined by the following rules, applied in order:

1. The imbalance $|D(J) - P(J)|$ must be as small as possible.
2. Among all juries with that minimum imbalance, the total $D(J) + P(J)$ must be as large as possible, so the jury is as valuable as possible to both sides.
3. If several juries still tie, choose the one whose list of candidate numbers, written in ascending order, comes first in "pseudo-alphabetic" order — that is, compare the sorted candidate lists as though the numbers were letters. For example $1,5,6,9$ comes before $2,3,4,5$ because $1 < 2$, and $1,2,3,5,9$ comes before $1,2,3,6,9$ because $5 < 6$.

Applied together, these three rules always single out exactly one jury. Write a program that carries out this selection.

The input contains several jury-selection rounds. Each round begins with a line containing two integers $n$ and $m$: the number of candidates and the number of jury members, with $1 \le n \le 200$, $1 \le m \le 20$, and $m \le n$. The next $n$ lines each contain two integers $p_i$ and $d_i$ — the prosecution's grade and the defence's grade for candidate $i$ — where $0 \le p_i, d_i \le 20$. A blank line may separate one round from the next.

The input ends with a round whose first line reads 0 0; that terminating round is not processed.

For each round, print a line Jury #r, where $r$ is the round number ($1, 2, \dots$).

On the next line print the prosecution total and the defence total in exactly this form (prosecution first, defence second):

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

Then, on the following line, print the numbers of the $m$ chosen candidates in ascending order, printing a single space before each number.

Print one blank line between consecutive rounds; there is no blank line before the first round and no blank line after the last.