Description

现今，社会上流行着各种各样的福利彩票，彩票已经融入到了人们的日常生活之中。彩票之所以能吸引那么多的人们，玩法多是一大原因。

小明五一放假和爸爸一起到广州游玩，发现了一种趣味彩票，玩法新颖，有别于传统的彩票形式。规则是这样的：

1．彩票中心每期随机产生N行M列整数（整数范围为-100~100）；

2．彩民选取1~10000之间的任意一个整数P，P即为选取的彩票号码；

3．彩票中心产生特等奖号码的规则如下：

(1)  从随机产生的N*M个数中选取M个数，每列必须选取一个，这样有NM种选法。

(2)在已选的M个数中，再选取若干个连续的数，如果这些数的和是NM种选法中所有连续序列里最大的，则称之为“幸运号码序列”。

(3)计算“幸运号码序列”的和，得到特等奖号码。

彩票中心请小明来编这个程序----计算特等奖号码，可是小明学习编程不久，你能帮助小明完成这个艰巨的任务吗？

Input Format

输入文件共有N+1行：

第1行有两个数：N(1<=N<=100)和M(1<=M<=10001)，中间用空格隔开；

第2行至第N+1行：每行为随机产生的M个整数。

Output Format

输出文件共有2行：

第1行：特等奖号码；

第2行：“幸运号码序列”中数的个数

注意：若有多组“幸运号码序列”可以得到特等奖号码，输出其中能组合成的最多个数。

3 5
-50 -47 36 -30 -23
17 -19 -34 -13 -8
-42 -3 -43 34 -45

84
4

Hint

 数据规模 

20%的数据：M<=1000

40%的数据：M<=5000

100%的数据：M<=10001

Source

贪心 前缀和