该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P1854 花店橱窗布置

题目描述

有 $N \times M$ 的矩阵，每行选一个数，且所选数所在的列数须递增（必须大于上一行所选数的列数，除了第一行）。

求所选数之和的最大值，并输出每行所选数的位置。

若有多种方案，输出字典序较小的方案。

输入格式

第一行是两个整数 $N \ M(1\le N\le M\le 5000)$。

下来是矩阵 $a_{i,j} \ (|a_{i,j}| \le 100)$。

说明：
int N[]={500, 1000, 2000, 3000, 4000};
int M[]={1000, 2000, 3000, 5000, 5000};

输出格式

第一行是一个整数，为最大值；

下来一行 $N$ 个整数。

输入输出样例 #1

输入 #1

3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20

输出 #1

53
2 4 5