#include <iostream>
using namespace std;
const int N = 20;
int dp[N][N];//dp[i][j]选到第i家店 一共卖了j本书的最大盈利
int g[N][N];
int path[N][N][N];//path[i][j][k]选到第i家店 一共卖了j本书, 第k家店卖了多少本

int main()
{
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
            cin>>g[i][j];
    
    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
            for(int k = 0; k <= j; k ++ )
            {
                /*
                因为k是从小到大枚举的
                所以若存在多个相同的 k 使得 dp[i][j] 最大
                则只有第一个（即最小的）k 的分配方案可以被传递过来
                这样就保证了分配方案字典序最小
                */
                if(dp[i - 1][k] + g[i][j - k] > dp[i][j])
                {
                    dp[i][j] =  dp[i - 1][k] + g[i][j - k];
                    path[i][j][i] = j - k;
                    //更新后 之前每家店卖了多少都要更新
                    for(int p = 1; p < i; p ++ )
                        path[i][j][p] = path[i - 1][k][p];
                }

            }

    cout<<dp[n][m]<<endl;
    for(int i = 1; i <= n; i ++ )
        cout<<i<<" "<<path[n][m][i]<<endl;
}