A Fair Jury

In the country of Brutopia, court verdicts are decided by a jury of ordinary citizens. Before each trial a jury must be chosen from a pool of candidates.

For every candidate $i$ in the pool, the prosecution assigns a value $p_i$ and the defense assigns a value $d_i$, each an integer from $0$ to $20$. A higher value means that party considers the candidate more suitable.

You must choose a jury $J$ of exactly $m$ candidates. For a chosen jury $J$ define

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

so $D(J)$ is the total defense value and $P(J)$ the total prosecution value of the jury.

To keep the trial fair, the jury should favour neither side, so $|D(J) - P(J)|$ must be as small as possible. Among all juries that reach this smallest possible difference, the jury should be as valuable as possible to both parties, that is $D(J) + P(J)$ should be as large as possible.

Given the pool of candidates, determine these two optimal quantities.

The input consists of several jury-selection rounds.

Each round begins with a line containing two integers $n$ and $m$: the number of candidates and the required number of jury members, with $1 \le n \le 200$, $1 \le m \le 20$, and $m \le n$.

Each of the next $n$ lines contains two integers $p_i$ and $d_i$ ($0 \le p_i, d_i \le 20$): the prosecution value and the defense value of candidate $i$.

Rounds may be separated by blank lines. The input ends with a round whose line reads 0 0, which must not be processed.

For each round, output three lines.

The first line is Jury #k, where k is the round number counting from 1. The second line reports the smallest achievable difference. The third line reports the largest achievable total among the juries that reach that smallest difference.

Print the two values using exactly this format:

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

Here X is the minimum possible value of |D(J) - P(J)|, and Y is the maximum possible value of D(J) + P(J) over all juries achieving that minimum difference.

Print one blank line after every round.

A jury of exactly $m$ members always exists because $m \le n$. A brute-force search over all $\binom{n}{m}$ juries is far too slow for the given limits; an efficient approach, for example dynamic programming over the possible values of $D(J) - P(J)$, is required.