작은 꽃집

꽃집 진열창을 가장 보기 좋게 꾸미려고 한다. 서로 다른 종류의 꽃다발이 $F$개 있고, 한 줄로 놓인 꽃병이 적어도 $F$개 있다. 꽃병은 선반에 고정되어 있으며 왼쪽에서 오른쪽으로 $1$번부터 $V$번까지 번호가 매겨져 있다. 즉 $1$번 꽃병이 가장 왼쪽, $V$번 꽃병이 가장 오른쪽이다. 꽃다발은 옮길 수 있으며 $1$번부터 $F$번까지의 정수로 구분된다.

이 번호는 놓이는 순서를 정한다. $i < j$이면 꽃다발 $i$는 반드시 꽃다발 $j$가 놓인 꽃병보다 왼쪽에 있는 꽃병에 놓여야 한다. 예를 들어 진달래($1$번), 베고니아($2$번), 카네이션($3$번)이 있다면, 진달래는 베고니아보다 왼쪽에, 베고니아는 카네이션보다 왼쪽에 놓여야 한다. 꽃병이 꽃다발보다 많으면 남는 꽃병은 비워 둔다. 꽃병 하나에는 꽃다발을 최대 하나만 놓을 수 있다.

꽃병마다 개성이 달라서, 특정 꽃다발을 특정 꽃병에 놓으면 정수로 표현되는 미적 가치가 생긴다. 꽃다발 $i$를 꽃병 $j$에 놓았을 때의 미적 가치를 $A_{i,j}$라고 하자. 꽃병을 비워 두면 미적 가치는 $0$이다.

예를 들어 미적 가치가 다음과 같다고 하자.

이 표에서 진달래는 꽃병 2에 두면 아주 보기 좋지만 꽃병 4에 두면 보기 흉하다.

정해진 순서를 지키면서 미적 가치의 합이 최대가 되도록 모든 꽃다발을 놓아라.

• 첫째 줄에 두 정수 $F$와 $V$가 주어진다.
• 다음 $F$개의 줄에는 각각 $V$개의 정수가 주어진다. $(i+1)$번째 줄의 $j$번째 정수는 꽃다발 $i$를 꽃병 $j$에 놓았을 때의 미적 가치 $A_{i,j}$이다.

• 첫째 줄에 얻을 수 있는 미적 가치 합의 최댓값을 출력한다.
• 둘째 줄에는 그 최댓값을 이루는 배치를 $F$개의 정수로 출력한다. $k$번째 정수는 꽃다발 $k$가 놓인 꽃병의 번호이다. 최댓값을 이루는 배치가 여러 개이면 사전순으로 가장 작은 것을 출력한다. 즉 꽃다발 $1, 2, \dots, F$의 꽃병 번호를 차례로 나열한 수열을 비교하여, 처음으로 달라지는 위치에서 더 작은 수열을 출력한다.

• $1 \le F \le 100$이며, $F$는 꽃다발의 개수로 꽃다발은 $1$번부터 $F$번까지 번호가 매겨진다.
• $F \le V \le 100$이며, $V$는 꽃병의 개수이다.
• $-50 \le A_{i,j} \le 50$이며, $A_{i,j}$는 꽃다발 $i$를 꽃병 $j$에 놓았을 때의 미적 가치이다.