题目描述

有F束花和从左到右排列的V个花瓶。花束编号为1至F，花瓶编号为1至V。每个花瓶最多放一束花，所有花束都必须放入花瓶。

编号较小的花束必须放在编号较小的花瓶中。第i束花放入第j个花瓶的美学值为A[i][j]，空花瓶贡献0。求最大总美学值，并输出一种摆放方案。

输入格式

第一行两个整数F、V。接下来F行，每行V个整数，表示美学值矩阵。

输出格式

第一行输出最大总美学值。第二行输出F个整数，第i个整数表示第i束花所在的花瓶编号。

本题使用特殊评测，有多种最优方案时输出任意一种。

样例

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

53
2 4 5

数据范围

1≤F≤V≤100；-50≤A[i][j]≤50。