/*

给定辩控双方给每个人的打分p[i],d[i]，

dp[j][k]表示前i个人有j个被选定，选定的人的辩控双方打分差之和是k，此状态下的最大辩控双方和

按01背包做，体积一维是1，体积二维是辩控双方打分差，价值是辩控双方打分和

要求体积一维不得超过m，体积二维在体积一维=m的情况下最小

状态转移方程：dp[j][k]=max(dp[j][k],dp[j-1][k-(a[i]-b[i])]+a[i]+b[i])

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#include<vector>

using namespace std;

struct node{

    int a,b,sum,dif;

}p[];

int dp[][];

int main(){

    int n,m,tt=;

    while(scanf("%d%d",&n,&m),n){

        memset(dp,-,sizeof dp);

        vector<int> path[][];

        for(int i=;i<=n;i++){

            scanf("%d%d",&p[i].a,&p[i].b);

            p[i].sum=p[i].a+p[i].b;

            p[i].dif=p[i].a-p[i].b;

        }

        int max_diff=m*;//由于两者之差可能是负数，所以在所有差值上增加一个max_diff

        dp[][max_diff]=;

        for(int i=;i<=n;i++)

            for(int j=m;j>=;j--)//逆序枚举，保证每个候选人最多被选一次

                for(int k=;k<=max_diff*;k++)

                    if(dp[j-][k]>=)

                        if(dp[j-][k]+p[i].sum>dp[j][k+p[i].dif]){

                            dp[j][k+p[i].dif]=dp[j-][k]+p[i].sum;

                            path[j][k+p[i].dif]=path[j-][k];

                            path[j][k+p[i].dif].push_back(i);

                        }

        int i,min_diff;

        for(i=;i<=max_diff;i++)

            if(dp[m][max_diff-i]>=||dp[m][max_diff+i]>=) break;

        //找到最小的差 i

        if(dp[m][max_diff-i]>dp[m][max_diff+i]) min_diff=max_diff-i;

        else min_diff=max_diff+i;

        cout << (dp[m][min_diff]+i)/ << " " <<(dp[m][min_diff]-i)/ << endl;

        for(int i=;i<m;i++)

            cout << path[m][min_diff][i] << " ";

        puts(" ");

    }

}