#include <bits/stdc++.h>
#define int long long
using namespace std;
    long long powmod(long long a,long long b,long long mod) {
        if (b==0 || a==1)  {if (mod==1) return 0; else return 1; }

        if (b%2==0) { long long k=powmod(a,b/2,mod); return (k*k)%mod; }
        else {long long k=powmod(a,b/2,mod); return ( (k*k) %mod *a)% mod; }
    }
    long long gcd(long long a, long long b) {
        if (a==0) return b;
        if (b==0) return a;
        if (a>b) return gcd(a%b,b); else return gcd(b%a,a);
    }
    int prime(int p) { // 1 - простое
        for (int i=2;i*i<=p;i++) {
            if (p%i==0 && i<p) return i;
        }
        return 1;
    }
    long long sqr(long long i) {
        return i*i;
    }

    void solve () {


         /* --------- */

    int a,b;
    cin>>a>>b;
    int m[2][a];


    for (int i=0;i<a;i++) {
        cin>>m[0][i]>>m[1][i];

    }
    int dp[a][4][b+1];
    for (int i=0;i<a;i++) {
        for (int j=0;j<4;j++) {
            for (int k=0;k<=b;k++) dp[i][j][k]=-1000000000000000;
        }
    }
dp[0][0][0]=0;
    pair<int,pair<int,int>> from[a][4][b+1];
    dp[0][3][1]=m[0][0]+m[1][0];
    for (int i=1;i<a;i++) {

            for (int k=0;k<=min(b,i+1);k++) {
                dp[i][0][k]=dp[i-1][0][k]; from[i][0][k]={i-1,{0,k}};
                if (dp[i-1][1][k]>dp[i][0][k]) {dp[i][0][k]=dp[i-1][1][k]; from[i][0][k]={i-1,{1,k}};}
                if (dp[i-1][2][k]>dp[i][0][k]) {dp[i][0][k]=dp[i-1][2][k]; from[i][0][k]={i-1,{2,k}};}
                if (dp[i-1][3][k]>dp[i][0][k]) {dp[i][0][k]=dp[i-1][3][k]; from[i][0][k]={i-1,{3,k}};}

                if (k>=1) { dp[i][1][k]=max(dp[i-1][2][k-1],dp[i-1][0][k-1])+m[0][i]+m[0][i-1];
                if (dp[i-1][2][k-1]>dp[i-1][0][k-1]) from[i][1][k]={i-1,{2,k-1}}; else from[i][1][k]={i-1,{0,k-1}}; }


                if (k>=1) { dp[i][2][k]=max(dp[i-1][1][k-1],dp[i-1][0][k-1])+m[1][i]+m[1][i-1];
                    if (dp[i-1][1][k-1]>dp[i-1][0][k-1]) from[i][2][k]={i-1,{1,k-1}}; else from[i][2][k]={i-1,{0,k-1}};
                }
                if (k>=1) { dp[i][3][k]=max({dp[i-1][0][k-1],dp[i-1][1][k-1],dp[i-1][2][k-1],dp[i-1][3][k-1]})+m[0][i]+m[1][i];
                int qq=max({dp[i-1][0][k-1],dp[i-1][1][k-1],dp[i-1][2][k-1],dp[i-1][3][k-1]});
                if (dp[i-1][0][k-1]==qq) from[i][3][k]={i-1,{0,k-1}};
                if (dp[i-1][1][k-1]==qq) from[i][3][k]={i-1,{1,k-1}};
                if (dp[i-1][2][k-1]==qq) from[i][3][k]={i-1,{2,k-1}};
                if (dp[i-1][3][k-1]==qq) from[i][3][k]={i-1,{3,k-1}};
                }

                }



            }


    int ans[2][a];
    for (int i=0;i<2;i++) for (int j=0;j<a;j++) ans[i][j]=0;
   int qq=max({dp[a-1][0][b],dp[a-1][1][b],dp[a-1][2][b],dp[a-1][3][b]});
  // cout<<qq<<" ";
   int curk=b;
   int curprof=0;
   if (dp[a-1][0][b]==qq) curprof=0;
   if (dp[a-1][1][b]==qq) curprof=1;
   if (dp[a-1][2][b]==qq) curprof=2;
   if (dp[a-1][3][b]==qq) curprof=3;

   for (int i=a-1;i>=1;i--) {
       if (curprof==0) {
           curprof=from[i][0][curk].second.first;
       } else if (curprof==1) {
           curprof=from[i][1][curk].second.first;
           ans[0][i]=curk;
           ans[0][i-1]=curk;
           curk--;
       }
       else if (curprof==2) {
           curprof=from[i][2][curk].second.first;
           ans[1][i]=curk;
           ans[1][i-1]=curk;
           curk--;
       } else if (curprof==3) {
           curprof=from[i][3][curk].second.first;
           ans[0][i]=curk; ans[1][i]=curk;
           curk--;
       }

   }
   if (curk>=1) { ans[0][0]=1; ans[1][0]=1; }
   for (int i=0;i<a;i++) cout<<ans[0][i]<<" "<<ans[1][i]<<"\n";
    /* --------- */
          return;
    }



    signed main() {

        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);



          int tututu;
          tututu=1;
       // cin>>tututu; // если нет запросов, то закоментить
          for (int qwerty=0;qwerty<tututu;qwerty++) solve();


        return 0;
    }