#include <iostream>#include <stdio.h>#include <algorithm>#include <string.h>using namespace std;int p[201],d[201],result[21];int dp[21][801],path[21][801];int cmp(const void *a,const void *b){ return *(int *)a-*(int *)b;}bool select(int a,int b,int i){ while(a>0 && path[a][b]!=i){ b-=p[path[a][b]]-d[path[a][b]]; a--; } return (a!=0)?true:false;}int main(){ int i,j,k,a,b,n,m,origin,ca=1; while(scanf("%d %d",&n,&m),n||m){ for(i=1;i<=n;i++) scanf("%d %d",p+i,d+i); memset(dp,-1,sizeof(dp)); memset(path,0,sizeof(path)); origin=m*20; for(dp[0][origin]=j=0;j<m;j++) for(k=0;k<=origin*2;k++) if(dp[j][k]>=0){ for(i=1;i<=n;i++) if(dp[j+1][k+p[i]-d[i]]<dp[j][k]+p[i]+d[i]){ a=j,b=k; if(!select(a,b,i)){ dp[j+1][k+p[i]-d[i]]=dp[j][k]+p[i]+d[i]; path[j+1][k+p[i]-d[i]]=i; } } } for(i=origin,j=0;dp[m][i+j]<0 && dp[m][i-j]<0;j++); k=dp[m][i+j]>dp[m][i-j]?i+j:i-j; printf("Jury #%dn",ca++); printf("Best jury has value %d for prosecution and value %d for defence:n",(dp[m][k]+k-origin)/2, (dp[m][k]-k+origin)/2); for(i=1;i<=m;i++){ result[i]=path[m-i+1][k]; k-=p[result[i]]-d[result[i]]; } qsort(result+1,m,sizeof(int),cmp); for(i=1;i<=m;i++) printf(" %d",result[i]); printf("n"); printf("n"); } return 0;}
