SP6819 ASSIGN5 - Yet Another Assignment Problem

新学期要开始了。班长 Cathy Yin 需要为班级准备一些工作。她面临 $m$ 项任务需要完成，$n$ 名同学将参与帮忙。每项任务需要一些同学协作完成，具体来说，第 $i$ 名同学需要在第 $j$ 项任务上工作 $A_{ij}$ 分钟。作为一个有责任感的信息学竞赛选手，Cathy 希望尽快完成所有任务。需要注意的是，一个同学同一时间只能做一项任务，且两位同学不能同时从事同一项工作。例如，为了装饰教室，Alpha 需要工作 3 分钟，而 Beta 需要工作 4 分钟，那么一种可能的安排是按照ABABBAB的顺序，总共耗时7分钟。 现在，她需要一个详细的计划来安排每位同学每时每刻要做什么。任务之间是独立的，完成顺序可以自由选择。对于每项任务，每位同学可以在限制范围内任意工作，但不能超过 $A_{ij}$ 分钟。任何同学都可以随时空闲，而且做某项工作并不要求时间连续。 作为她的朋友，请帮助 Cathy 制定出一个计划，使得完成所有任务所需的总时间最小化。

第一行输入包含两个正整数 $m$ 和 $n$，表示任务数量和同学数量（$1 \le m, n \le 2000$）。 接下来的 $m$ 行，每行描述一项任务。第 $i$ 行包含 $n$ 个非负整数（$\le 10^6$），其中第 $j$ 个数是 $A_{ij}$，表示第 $j$ 位同学需要在第 $i$ 项任务上工作 $A_{ij}$ 分钟。

输出第一行包含一个整数 $T$，表示完成所有任务所需的最短时间。第二行输出 $n$ 个非负整数（$\le m$），表示第一分钟内每个同学的安排，其中第 $i$ 个数表示第 $i$ 位同学正在进行的任务编号，0 表示该同学空闲。 如果有多种方案，输出任意一个即可。

- $1 \le m, n \le 2000$ - $0 \le A_{ij} \le 10^6$ **本翻译由 AI 自动生成**