Hotel

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

inputFormat

input will give each hotel a D night's room rate.

outputFormat

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

样例

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

21980 1
2
1
1
1

</p>