Problem Statement

Mr. Takatsuki, who is planning to participate in the Aizu training camp, has a poor house and does not have much money. She is looking for a hotel for a training camp, but is struggling to make a plan that saves as much money as possible. Let's tell her how to stay at a hotel where the total amount of accommodation will be cheaper.

The number of hotel candidates to stay is N, and each hotel is called Hotel 1, Hotel 2, ..., Hotel N. She is now choosing from these hotels to book for D nights. For all candidate hotels, the room rate may fluctuate per night, so the input will give each hotel a D night's room rate.

Output how to stay at the hotel so that the total accommodation cost for D nights is minimized. However, please note that it is not necessary to stay at the same hotel for all D nights. For the sake of cheapness, she is also considering moving to a hotel every night.

If there are multiple such accommodation methods, output the accommodation method that minimizes the number of trips to the hotel. The number of hotel trips is the value obtained by adding up D nights, considering that this is considered as one trip when the hotel staying at the xth night (1 <= x <D) and the hotel staying at the x + 1 night are different. Is.

If you still cannot find one, output the accommodation method that is the smallest in the dictionary order. When there is a sequence of two hotel numbers A = {a1, a2, ..., aD} and B = {b1, b2, ..., bD}, it means that A is smaller than B in lexicographical order. For the first i such that ai is different from bi, say when ai is smaller than bi.

Constraints

* 1 <= N <= 50
* 1 <= D <= 50
* 1 <= pij <= 10000

Input

Each data set is input in the following format.


N D
p11 p12 ... p1D
p21 p22 ... p2D
...
pN1 pN2 ... pND


All inputs are integers. N is the number of hotel candidates for accommodation, and D is the number of nights. pij is the accommodation fee for the jth night at Hotel i.

Output

Output in the following format for each dataset.


P M
stay1
stay2
...
stayD


P is the minimum total accommodation cost for D nights, and M is the minimum number of hotel trips. Next, determine the hotel to stay under the conditions specified in the problem statement, and output the hotel number for D nights. stayi (1 <= stayi <= N) means that the hotel staying at the i night is the hotel stayi.

Examples

Input

2 3
3000 6000 3000
4000 5500 4500


Output

11500 2
1
2
1


Input

3 4
5500 5500 5500 5500
5480 5780 5980 5980
5500 5500 5500 5500


Output

21980 1
2
1
1
1
#include<iostream>
#include<algorithm>
#include<vector>
#include<cassert>
#include<cstdio>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define inf (1<<29)
#define MAX 100
using namespace std;
typedef long long ll;

/*
経路復元用
dp[day][hotel][number] := minimum
 */
int dp[MAX][MAX][MAX];
int path[MAX][MAX][MAX];
int N,D,p[MAX][MAX];

int main()
{
  scanf("%d %d",&N,&D);
  rep(i,N)
    {
      rep(j,D)scanf("%d",&p[i][j]);
      reverse(p[i],p[i]+D);
    }
  
  rep(i,D+1)rep(j,N)rep(k,55)
    {
      dp[i][j][k] = inf;
      path[i][j][k] = inf;
    }

  rep(i,N)dp[0][i][0] = 0;

  rep(day,D)
    {
      rep(hotel,N)
	{
	  rep(number,55)
	    {
	      if(dp[day][hotel][number] == inf)continue;
	      rep(next_hotel,N)
		{
		  int add = (hotel != next_hotel);
		  if(dp[day+1][next_hotel][number+add] > dp[day][hotel][number]+p[next_hotel][day])
		    {
		      dp[day+1][next_hotel][number+add] = dp[day][hotel][number]+p[next_hotel][day];
		      path[day+1][next_hotel][number+add] = hotel;
		    }
		  else if(dp[day+1][next_hotel][number+add] == dp[day][hotel][number]+p[next_hotel][day])
		    {
		      if(path[day+1][next_hotel][number+add] > hotel)path[day+1][next_hotel][number+add] = hotel;
		    }
		}
	    }
	}
    }

  int mincost,minnumber,minN;
  mincost = minnumber = minN = inf;

  rep(i,N)rep(j,55)
    {
      if(mincost >= dp[D][i][j])
	{
	  if(mincost == dp[D][i][j])
	    {
	      if(minnumber >= j)
		{
		  if(minnumber == j)
		    {
		      if(minN > i)
			minN = i;
		    }
		  else
		    {
		      minnumber = j;
		      minN = i;
		    }
		}
	    }
	  else
	    {
	      mincost = dp[D][i][j];
	      minnumber = j;
	      minN = i;
	    }
	}
    }

  cout << mincost << " " << minnumber << endl;
  vector<int> ph;
  int d,h,n;

  d = D,h = minN, n = minnumber;

  int diff = p[h][D-1];
  for(;d >= 0 && n >= 0;)
    {
      ph.push_back(h);

      int next_h = path[d][h][n];
      int next_n = n - (next_h != h);
      h = next_h;
      n = next_n;
      d--;
      diff += p[h][d-1];
      if(path[d][h][n] == inf)break;
    }
  rep(i,ph.size())
    {
      cout << ph[i]+1 << endl;
      assert(ph[i]!=inf);
    }
  return 0;
}