/* Skrevet av Dag Langmyhr (dag@ifi.uio.no)
   til NM i programmering 2000. */

#include <stdio.h>
#include <stdlib.h>

#define DEBUG

int p[201], d[201], cur[21], best[21], 
    best_sum_p, best_sum_d, m, n;


int better(int diff1, int diff2, int sum1, int sum2)
{
  int i;

  /* Is (diff1,sum1) a better solution than (diff2,sum2)? */

  if (abs(diff1) != abs(diff2)) return abs(diff1)<abs(diff2);
  if (abs(sum1)  != abs(sum2))  return abs(sum1)>abs(sum2);
  for (i = 1;  i <= m;  ++i) {
    if (cur[i] != best[i]) return cur[i]<best[i];
  }
  return 0;
}


void test(int sum_p, int sum_d, int ix, int n_sel)
{
  /* Test for a better solution:
     sum_p:	sum of selected p's so far
     sum_d:	sum of selected d's so far
     ix:	current index
     n_sel:	no of selected jury members so far */

  int i;

#ifdef TESTING
  printf("n=%d, m=%d, sum_p=%d, sum_d=%d, ix=%d, n_sel=%d.\n",
	 n, m, sum_p, sum_d, ix, n_sel);
#endif

  if (n_sel == m) {
    /* Another solution has been found. */

    if (better(sum_p-sum_d, best_sum_p-best_sum_d, 
	       sum_p+sum_d, best_sum_p+best_sum_d)) {
#ifdef DEBUG
      printf("An improvement: diff=%d, sum=%d:\n", 
	     abs(sum_p-sum_d), sum_p+sum_d);
      printf("               ");
      for (i = 1;  i <= m;  ++i) printf(" %d", cur[i]);
      printf("\n");
#endif
      best_sum_p = sum_p;  best_sum_d = sum_d;
      for (i = 1;  i <= m;  ++i) best[i] = cur[i];  
    }
  } else {
    /* First, try not selecting element `ix': */

    if (m-n_sel <= n-ix) test(sum_p, sum_d, ix+1, n_sel);

    /* Then, try selecting it: */

    cur[n_sel+1] = ix;
    if (m-n_sel-1 <= n-ix) test(sum_p+p[ix], sum_d+d[ix], ix+1, n_sel+1);
  }
}


int main(void)
{
  FILE *in_f  = fopen("infil.E","r"),
       *out_f = fopen("utfil.E","w");
  int  n_juries = 0, i;

  fscanf(in_f, "%d%d", &n, &m);
  while (m > 0) {
    for (i = 1;  i <= n;  ++i) fscanf(in_f, "%d%d", &p[i], &d[i]);
    best_sum_p = 99999;  best_sum_d = 0;  test(0, 0, 1, 0);

    fprintf(out_f, "Jury #%d\n", ++n_juries);
    fprintf(out_f, 
	    "Best jury has value %d for prosecution\nand %d for defence:\n",
	    best_sum_p, best_sum_d);
    for (i = 1;  i <= m;  ++i) fprintf(out_f, " %d", best[i]);
    fprintf(out_f, "\n\n");
    
    fscanf(in_f, "%d%d", &n, &m);
  }

  fclose(in_f);  fclose(out_f);  return 0;
}