# Jury Compromise

Time Limit: 10 Seconds Memory Limit: 32768 KB

Special Judge

Based on the grades of the two parties, the judge selects the jury. In order to ensure a fair trial, the tendencies of the jury to favour either defence or prosecution should be as balanced as possible. The jury therefore has to be chosen in a way that is satisfactory to both parties.

We will now make this more precise: given a pool of n potential jurors and two values di (the defence's value) and pi (the prosecution's value) for each potential juror i, you are to select a jury of m persons. If J is a subset of {1, ..., n} with m elements, then D(J) = sum dk (k in J) and P(J) = sum pk (k in J) are the total values of this jury for defence and prosecution.

For an optimal jury J, the value | D(J) - P(J) | must be minimal. If there are several jurys with minimal | D(J) - P(J) |, one which maximizes D(J) + P(J) should be selected since the jury should be as ideal as possible for both parties.

You are to write a program that implements this jury selection process and chooses an optimal jury given a set of candidates.

Note: If your solution is based on an inefficient algorithm, it may not execute in the allotted time.

## Input

The input contains several jury selection rounds. Each round starts with a line containing two integers n and m. n is the number of candidates and m the number of jury members. These values will satisfy 1 <= n <= 200, 1 <= m <= 20 and of course m <= n. The following n lines contain the two integers pi and di for i = 1, ..., n. A blank line separates each round from the next.

The input ends with a round that has n = m = 0.

## Output

For each round output a line containing the number of the jury selection round (`Jury #1', `Jury #2', etc.).

On the next line print the values D(J) and P(J) of your jury as shown below and on another line print the numbers of the m chosen candidates in ascending order. Output a blank before each individual candidate number.

Output an empty line after each test case.

## Sample Input

4 2 1 2 2 3 4 1 6 2 0 0

## Sample Output

Jury #1 Best jury has value 6 for prosecution and value 4 for defence: 2 3Submit

Source: Southwest Europe 1996