学步园

//dp，其实和背包有点差不多
//f[i][j]，i表示物品数（对应每一组辩控值），j表示辩控差，f[i][j]表示辩控和
//i的最大取值为m,用n种物品不断去试 
//参考代码： http://www.cnblogs.com/rainydays/archive/2011/07/21/2113240.html
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;

int n,m;
int path[25][25*20*2];
int f[25][25*20*2];
//visited元素个数写成25了，WA了几次 
int visited[205];
int pi[205];
int di[205];
int stack[25];

//查找路径上哪些物品已经使用过了 
void findPath(int i,int j){
    //为了取得某条路径，首先全部初始化为未访问过 
    memset(visited,0,sizeof(visited));
    while(path[i][j]!=-1){
        int k=path[i][j];
        visited[k]=1;
        i--;
        j-=(pi[k]-di[k]);
    } 
}

//将节点k加入进去 
void make(int i,int j,int k){
    int a=pi[k]+di[k];
    int b=pi[k]-di[k];
    if(f[i+1][j+b]==-1||f[i+1][j+b]<f[i][j]+a){
        f[i+1][j+b]=f[i][j]+a;
        path[i+1][j+b]=k;
    }
}

int main(){
    int t=0;
    while(scanf("%d%d",&n,&m)!=EOF){
        if(m==0&&n==0)
            break;
        t++;
        for(int i=0;i<n;i++)
            scanf("%d%d",&pi[i],&di[i]);
        
        printf("Jury #%d\n",t);
        memset(path,-1,sizeof(path));
        memset(f,-1,sizeof(f));
        memset(visited,0,sizeof(visited));
        int w=m*20;//初始状态 
        f[0][w]=0;
        
        for(int i=0;i<m;i++)
            for(int j=0;j<=2*w;j++){
                //可以向里面放东西了 
                if(f[i][j]!=-1){
                    //确定哪些物品已经使用过
                    findPath(i,j);
                    for(int k=0;k<n;k++){
                        if(visited[k]==0){
                            make(i,j,k);
                        }
                    }//end for
                }//end if
            }//end for
        int left=-1,right=-1,pos;
        for(int i=0;i<=w;i++){
            //寻找第一个距离w最小的可能的差值 
            if(f[m][w+i]!=-1){
                right=i;
                break;
            }
        }
        for(int i=0;i<=w;i++){
            if(f[m][w-i]!=-1){
                left=i;
                break;
            } 
        }
        //判断结果
        if(right==-1||(left<right)&&left!=-1)
            pos=w-left;
        else if(left==-1||(right<left)&&right!=-1)
            pos=w+right;
        else if(f[m][w+right]>f[m][w-left])
            pos=w+right;
        else
            pos=w-left;
        int a=f[m][pos];
        int b=pos-w;
        int ansp=(a+b)>>1;
        int ansd=(a-b)>>1;
        printf("Best jury has value %d for prosecution and value %d for defence:\n", ansp, ansd);
        int top=0;
        a=m;
        b=pos;
        while(path[a][b]!=-1){
            int k=path[a][b];
            stack[top++]=k;
            a--;
            b-=(pi[k]-di[k]);
        }
        sort(stack,stack+top);
        for(int i=0;i<top;i++)
            printf(" %d",stack[i]+1);
        printf("\n");
        printf("\n");
    }
    return 0;
}