#include<bits/stdc++.h> using namespace std; int f[11][16],graph[11][16],path[11][16][11],n,m; int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) cin>>graph[i][j]; } memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=j;k++) { if (f[i][j]<f[i-1][j-k]+graph[i][k]) { f[i][j]=f[i-1][j-k]+graph[i][k]; for(int h=1;h<i;h++) path[i][j][h]=path[i-1][j-k][h];//path数组只有在状态发生转移时才更新 path[i][j][i]=k; } } cout<<f[n][m]<<endl; for(int i=1;i<=n;i++) cout<<i<<" "<<path[n][m][i]<<endl; return 0; }