#include <iostream>
#include <cstring>
using namespace std;
const int N = 16;
int n, m;
int f[N][N];
int w[N][N];
int g[N][N];

/*
递归思想解决逆序输出
*/

void show(int x, int y)
{
    if(x == 0)
        return;
    show(x-1, y-g[x][y]);
    cout << x << ' ' << g[x][y] << endl;
}

int main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin >> w[i][j];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            f[i][j] = f[i-1][j];
            for(int k=1; k<=m; k++)
                if(j >= k)
                {
                    if(f[i-1][j-k]+w[i][k] >= f[i][j])
                    {
                        f[i][j] = f[i-1][j-k]+w[i][k];
                        g[i][j] = k;
                    }
                }
        }

    cout << f[n][m] << endl;
    show(n, m); 
}