T43830 Chino的成绩

此题为汕头某中学dalao提供 由其学校内部赛原题改编，并非原题且并未公开 原出题人@月见之兔 曾经幻想过未来的风景 或许有着另外一片天 小镇的远方 有着深远的回忆 也有着富有深情的诗篇

Chino非常注重自己的成绩。 Chino有 $m$ 种方式给自己增加 $rp$ 以增加成绩，她的每种增加 $rp$ 的方式都有 $n$ 个阶段，第 $i$ 种的第 $j$ 个阶段增加的 $rp$ 表示为 $A_{ij}$，表示连续进行了 $j$ 天第 $i$ 种增加 $rp$ 的方式。 Chino连续进行同一种方式，效果可能更好也可能更差，她想要知道在 $n$ 天里能获得的最大 $rp$，你能帮帮可爱的Chino吗？

第一行，两个正整数 $n$，$m$。 接下来 $m$ 行，第 $i+1$ 行为 $n$ 个整数( $A_{i1} - A_{in}$ )。

一行一个数，最大的 $rp$。

本题分为3个Subtask。 第一个Subtask，2组数据 ，保证 $n \leq 50$， $m \leq 5000$， $a_i \leq 1e9$。 对于第二个Subtask，4组数据，保证 $n \leq 70$， $m \leq 10000$， $a_i \leq 1e9$。 对于第三个Subtask，4组数据，保证 $n \leq 100$， $m \leq 5000$， $a_i \leq 1e9$。 其中每组数据4分，对于每个Subtask及其中的每个数据点，取分数和。 ### 样例解释1 第 $1$ 天进行第 $1$ 项活动，获得 $A_{11}=3$ 点rp。 第 $2$ 天进行第 $2$ 项活动，获得 $A_{21}=3$ 点rp。 第 $3$ 天进行第 $1$ 项活动，获得 $A_{11}=3$ 点rp。 ### 样例解释2 第 $1$ 天进行第 $2$ 项活动，获得 $A_{21}=3$ 点rp。 第 $2$ 天进行第 $2$ 项活动，获得 $A_{22}=5$ 点rp（因为已经连续进行了 $2$ 次第 $2$ 项活动，因而是 $A_{22}$ 而不是 $A_{21}$ 。 第 $3$ 天进行第 $3$ 项活动，获得 $A_{31}=4$ 点rp。