#include<fstream>

#define MAXL 101
#define INF 2000

using namespace std;
typedef int var;

ifstream fin("lapte.in");
ofstream fout("lapte.out");

var DIN[MAXL][MAXL][MAXL]; // TIMPUL IN CARE SE BEAU i litri de L1, j litri de L2
var NRA[MAXL][MAXL][MAXL], NRB[MAXL][MAXL][MAXL];
var A[MAXL], B[MAXL];
var n;

    var L;

var din() {
    var tmin, lasti, lastj, cop, li, lj;
    bool a;

    for(var i=0; i<=L; i++) {
        for(var j=0; j<=L; j++) {
            if(!i && !j) continue;
            tmin = INF;
            for(var k=1; k<=n; k++) {
                li = i-1;
                lj = j-1;
                var MAX;
                if(i) {
                MAX = max(DIN[li][j][0], DIN[li][j][k] + A[k]);
                if(tmin > MAX) {
                    tmin = MAX;
                    lasti = li;
                    lastj = j;
                    cop = k;
                    a = 1;
                }
                }
                MAX = max(DIN[i][lj][0], DIN[i][lj][k] + B[k]);
                if(j) {
                    if(tmin > MAX) {
                    tmin = MAX;
                    lasti = i;
                    lastj = lj;
                    cop = k;
                    a = 0;
                }
                }
            }
            for(var k=1; k<=n; k++) {
                DIN[i][j][k] = DIN[lasti][lastj][k];
                NRA[i][j][k] = NRA[lasti][lastj][k];
                NRB[i][j][k] = NRB[lasti][lastj][k];
            }
            if(a) {
                DIN[i][j][cop] +=A[cop];
                NRA[i][j][cop] ++;
            }
            else {
                DIN[i][j][cop] += B[cop];
                NRB[i][j][cop] ++;
            }
            DIN[i][j][0] = tmin;
        }
    }
    return DIN[L][L][0];
}

int main() {
    fin>>n>>L;
    for(var i=1; i<=n; i++) {
        fin>>A[i]>>B[i];
    }
    fout<<din()<<endl;
    for(var i=1; i<=n; i++) {
        fout<<NRA[L][L][i]<<" "<<NRB[L][L][i]<<'\n';
    }

    return 0;
}