1 /* 1619 */  2 #include <cstdio>  3 #include <cstring>  4 #include <cstdlib>  5   6 #define MAXN 15  7 #define MAXM 105  8 #define INF    9999999  9  10 int dp[MAXN][MAXM]; 11 int path[MAXN][MAXM]; 12 int map[MAXN][MAXM]; 13 int stack[MAXM], top; 14 int d[3]; 15 int ans; 16 int n, m; 17  18 void solve(int beg) { 19     int i, j, k, tmp; 20  21     for (i=0; i<n; ++i) 22         dp[i][m-1] = INF; 23     dp[beg][m-1] = map[beg][m-1]; 24     path[beg][m-1] = -1; 25  26     for (j=m-2; j>=0; --j) { 27         for (i=0; i<n; ++i) { 28             if (i == 0) 29                 d[0] = n - 1; 30             else 31                 d[0] = i - 1; 32             d[1] = i; 33             if (i == n-1) 34                 d[2] = 0; 35             else 36                 d[2] = i + 1; 37             if (dp[d[0]][j+1] == dp[d[1]][j+1]) { 38                 k = d[0]<d[1] ? d[0]:d[1]; 39                 if (dp[k][j+1] == dp[d[2]][j+1]) 40                     k = k<d[2] ? k:d[2]; 41                 else if (dp[k][j+1] < dp[d[2]][j+1]) 42                     k = k; 43                 else 44                     k = d[2]; 45             } else if (dp[d[0]][j+1] < dp[d[1]][j+1]) { 46                 if (dp[d[0]][j+1] == dp[d[2]][j+1]) 47                     k = d[0]<d[2] ? d[0]:d[2]; 48                 else if (dp[d[0]][j+1] < dp[d[2]][j+1]) 49                     k = d[0]; 50                 else 51                     k = d[2]; 52             } else { 53                 if (dp[d[1]][j+1] == dp[d[2]][j+1]) 54                     k = d[1]<d[2] ? d[1]:d[2]; 55                 else if (dp[d[1]][j+1] < dp[d[2]][j+1]) 56                     k = d[1]; 57                 else 58                     k = d[2]; 59             } 60             path[i][j] = k; 61             dp[i][j] = dp[k][j+1]; 62             if (dp[i][j] != INF) 63                 dp[i][j] += map[i][j]; 64         } 65     } 66  67     tmp = INF; 68     for (i=0; i<n; ++i) { 69         if (dp[i][0] < tmp) { 70             tmp = dp[i][0]; 71             k = i; 72         } 73     } 74  75     if (tmp < ans) { 76         ans = tmp; 77         top = 0; 78         j = 0; 79         stack[top++] = k + 1; 80         while (path[k][j] >= 0) { 81             stack[top++] = path[k][j] + 1; 82             k = path[k][j]; 83             ++j; 84         } 85     } 86 } 87  88 int main() { 89     int i, j, k, tmp; 90  91     #ifndef ONLINE_JUDGE 92         freopen("data.in", "r", stdin); 93         freopen("data.out", "w", stdout); 94     #endif 95  96     while (scanf("%d %d", &n, &m) != EOF) { 97         for (i=0; i<n; ++i) 98             for (j=0; j<m; ++j) 99                 scanf("%d", &map[i][j]);100         ans = INF;101         for (i=0; i<n; ++i)102             solve(i);103 104         for (i=0; i<m-1; ++i)105             printf("%d ", stack[i]);106         printf("%d\n", stack[m-1]);107         printf("%d\n", ans);108     }109 110     return 0;111 }