题目描述

你希望以最美观的方式布置花店的橱窗。现在有 $F$ 束不同种类的花，以及至少同样多数量的花瓶，这些花瓶排成一行并固定在架子上。花瓶按从左到右的顺序编号为 $1$ 到 $V$，其中 $V$ 是花瓶的总数，$1$ 是最左边的花瓶，$V$ 是最右边的花瓶。花束可以移动，并且每束花都有一个唯一的编号，范围在 $1$ 到 $F$ 之间。这些编号决定了花束在花瓶中的摆放顺序：对于任意两束花 $i$ 和 $j$，如果 $i < j$，那么花束 $i$ 必须放在花束 $j$ 左边的某个花瓶中。例如，假设你有三束花：编号为 $1$ 的杜鹃花（azaleas）、编号为 $2$ 的秋海棠（begonias）和编号为 $3$ 的康乃馨（carnations），那么杜鹃花必须放在秋海棠左边的某个花瓶中，而秋海棠必须放在康乃馨左边的某个花瓶中。如果花瓶数量多于花束数量，多余的花瓶将保持空置。每个花瓶只能放一束花。

每个花瓶具有独特的特性（就像花束一样），因此将某束花放入某个花瓶会产生一定的美观值，用一个整数表示。这些美观值以一个表格的形式给出，如下所示。空置的花瓶的美观值为 $0$。

根据表格，杜鹃花放在花瓶 $2$ 中会非常美观（美观值为 $23$），但放在花瓶 $4$ 中会非常难看（美观值为 $-24$）。

你的目标是找到一种摆放方案，使得所有花束的美观值之和最大，同时满足花束编号的顺序要求。如果存在多个最优方案，只需输出其中一种即可。

输入

第一行包含两个整数：$F$ 和 $V$。
接下来的 $F$ 行，每行包含 $V$ 个整数，表示美观值表格 $A_{ij}$，其中 $A_{ij}$ 是第 $i$ 束花放入第 $j$ 个花瓶的美观值。

输入约束：

• $1 \leq F \leq 100$，表示花束的数量，编号为 $1$ 到 $F$。
• $F \leq V \leq 100$，表示花瓶的数量。
• $-50 \leq A_{ij} \leq 50$，表示花束 $i$ 放入花瓶 $j$ 的美观值。

输出

第一行输出你的摆放方案的美观值之和的最大值。

样例输入

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

样例输出

53

来源

国际信息学奥林匹克竞赛（IOI）1999