#222. 花店橱窗

花店橱窗

题目描述

每种花都有一个标识,假设杜鹃花的标识数为1,秋海棠的标识数为2,康乃馨的标识数为3,所有的花束在放入花瓶时必须保持其标识数的顺序,即:杜鹃花必须放在秋海棠左边的花瓶中,秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目。则多余的花瓶必须空置,且每个花瓶中只能放一束花。

每种花放在不同的瓶子里会产生不同的美观程度,美观程度可能是正数也可能是负数。

上述例子中,花瓶与花束的不同搭配所具有的美观程度,如下表所示:

                         花    瓶

                  1     2    3    4    5
   1 (杜鹃花)     7    23   -5  -24   16
   2 (秋海棠)     5    21   -4   10   23
   3 (康乃馨)    -21    5   -4  -20   20


根据上表,杜鹃花放在花瓶2中,会显得非常好看;但若放在花瓶4中则显得十分难看。

为取得最大美观程度,你必须在保持花束顺序的前提下,使花束的摆放取得最大的美学值,并求出每种花应该摆放的花瓶的编号。

输入格式

第1行:两个整数F和V,表示xq和xz一共有F种花,V个花瓶。(1<=F<=V<=100) 第2行到第F+1行:每行有V个数,表示花摆放在不同花瓶里的美观程度值value。(美观程度和不超过maxint,美观程度有正有负。)

输出格式

输出有两行:第一行为输出最大美观程度和的值,第二行有F个数表示每朵花应该摆放的花瓶的编号。

样例输入

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

样例输出

53
2 4 5

提示

其实就是简单的DP,花店橱窗问题啦。 注意尽量靠前放啊!