#include<iostream>
#include<cstring>
using namespace std;
const int INF = -5000;
const int MAXC = 100;
const int MAXM = 100;
int V[MAXC+1][MAXM+1];
int B1[MAXC+1][MAXM+1];
int B2[MAXC+1][MAXM+1];
int B3[MAXC+1][MAXM+1];
int pre[MAXM+1];
int cur[MAXM+1];
int F1[MAXM+1];
int X[MAXC+1];
int BX[MAXC+1];
int bestValue = INF;
int C[MAXC+1][MAXM+1];
int Best_1(int n, int m);
int Best_2(int n, int m);
int Best_3(int n, int m);
void Show(int i, int j);
int Show_2(int n, int m);
void DFS(int n, int i, int j);
int MDFS(int i, int j);
void Show_3(int n, int m);
int main()
{
int n, m;
cin >> n >> m;
for (int i=1; i<=n; i++)
{
for (int j=1; j<=m; j++)
{
cin >> V[i][j];
}
}
cout << Best_1(n, m) << endl;
Show(n, m);
cout << Show_2(n, m) << endl;
cout << Best_2(n, m) << endl;
cout << Best_3(n, m) << endl;
DFS(n, n, m);
cout << bestValue << endl;
for (int i=1; i<=n; i++)
{
cout << BX[i] << " ";
}
cout << endl;
for (int i=1; i<=MAXC; i++)
{
for (int j=1; j<=MAXM; j++)
{
B2[i][j] = INF;
}
}
cout << MDFS(n, m) << endl;
Show_3(n, m);
return 0;
}
int Best_1(int n, int m)
{
for (int i=1; i<=n; i++)
{
for (int j=i; j<=m-n+i; j++)
{
int bestP = INF;
for (int k=i; k<=j; k++)
{
if (bestP < B1[i-1][k-1] + V[i][k])
bestP = B1[i-1][k-1] + V[i][k];
}
B1[i][j] = bestP;
}
}
return B1[n][m];
}
void Show(int i, int j)
{
if (i == 0 || j == 0)
return;
for (int k=j; k>=i; k--)
{
if (B1[i][j] == B1[i-1][k-1] + V[i][k])
{
Show(i-1, k-1);
cout << k << " ";
break;
}
}
}
int Show_2(int n, int m)
{
for (int i=n,j=m; i>0; i--)
{
for (int k=i; k<=j; k++)
{
if (B1[i][j] == B1[i-1][k-1] + V[i][k])
{
X[i] = k;
j = k - 1;
break;
}
}
}
int s = 0;
for (int i=1; i<=n; i++)
{
cout << X[i] << " ";
s += V[i][X[i]];
}
cout << endl;
return s;
}
int Best_2(int n, int m)
{
for (int i=1; i<=n; i++)
{
for (int j=i; j<=m-n+i; j++)
{
int bestP = INF;
for (int k=i; k<=j; k++)
{
if (bestP < pre[k-1] + V[i][k])
bestP = pre[k-1] + V[i][k];
}
cur[j] = bestP;
}
for (int j=i; j<=m-n+i; j++)
{
pre[j] = cur[j];
}
}
return pre[m];
}
int Best_3(int n, int m)
{
for (int i=1; i<=n; i++)
{
for (int j=m-n+i; j>=i; j--)
{
int bestP = INF;
for (int k=i; k<=j; k++)
{
if (bestP < F1[k-1] + V[i][k])
bestP = F1[k-1] + V[i][k];
}
F1[j] = bestP;
}
}
return F1[m];
}
void DFS(int n, int i, int j)
{
if (i==0 || j==0)
{
int s = 0;
for (int k=1; k<=n; k++)
{
s += V[k][X[k]];
}
if (bestValue < s)
{
bestValue = s;
for (int k=1; k<=n; k++)
{
BX[k] = X[k];
}
}
return;
}
for (int k=i; k<=j; k++)
{
X[i] == k;
DFS(n, i-1, k-1);
}
}
int MDFS(int i, int j)
{
if (B2[i][j] != INF)
return B2[i][j];
if (i==0 || j==0)
return 0;
int bestP = INF;
for (int k=i; k<=j; k++)
{
if (bestP < MDFS(i-1, k-1) + V[i][k])
bestP = MDFS(i-1, k-1) + V[i][k];
}
return B2[i][j] = bestP;
}
void Show_3(int n, int m)
{
int bestP, pos;
for (int i=1; i<=n; i++)
{
for (int j=i; j<=m-n+i; j++)
{
bestP = INF;
for (int k=i-1; k<j; k++)
{
if (bestP < B3[i-1][k] + V[i][j])
{
bestP = B3[i-1][k] + V[i][j];
C[i][j] = k;
}
}
B3[i][j] = bestP;
}
}
bestP = INF;
for (int j=n; j<=m; j++)
{
if (bestP < B3[n][j])
{
bestP = B3[n][j];
pos = j;
}
}
cout << bestP << endl;
for (int i=n; i>0; i--)
{
X[i] = pos;
pos = C[i][pos];
}
for (int i=1; i<=n; i++)
{
cout << X[i] << " ";
}
cout << endl;
}
