Emiya 是个擅长做菜的高中生,他会做 m 道不同的菜品。某天,Yaz、Zid 和他们的 n 个朋友们到他家做客,Emiya 需要做一些菜来招待他们。
Yaz 和 Zid 什么都吃,但他们的朋友们有些挑食。具体来说,我们用整数 ai,j≥−1 来表示第 i 个朋友对第 j 道菜品的态度:
- 若 ai,j≥0,则第 i 位朋友不讨厌这道菜品,如果饭桌上有这道菜,且没有其他让这位朋友讨厌的菜品,那么他会给 Emiya 留下 ai,j 元红包以表赞许和感谢。
- 若 ai,j=−1,则第 i 为朋友讨厌这道菜品,如果饭桌上有这道菜,那么这位朋友会非常生气,并直接离席而去。这意味着他将不会因为任何菜品留下红包。
Emiya 擅长做菜,却不擅长计算,请你帮助 Emiya 挑选若干道菜品,使得他收到的红包数额总和最大。方便起见,你只需要输出这个最大的总和即可。
输入格式
从标准输入读入数据。
第一行包含两个整数 n,m,意义见题目描述。
第 2 到第 n+1 行,每行包含 m 个整数:其中第 i+1 行的第 j 个整数为 ai,j,意义见题目描述。
保证 n,m≥1,保证 ai,j≥−1。
输出格式
输出到标准输出。
一行一个整数,表示红包金额的最大总和。
样例
输入
3 3
1 2 3
2 -1 100
100 10 -1
输出
113
解释
最优方案是制作第 1 和第 2 道菜。若如此做,虽然第 2 位客人会生气地离席而去,但另两位客人留下的红包总金额是最大的。
样例二
见下载目录下的 ex_2.in 与 ex_2.ans。
样例三
见下载目录下的 ex_3.in 与 ex_3.ans。
子任务
本题设置 4 个子任务:
- 第 1 个子任务(20 分)的特殊限制:n≤10,m≤2000;
- 第 2 个子任务(20 分)的特殊限制:n≤14;
- 第 3 个子任务(20 分)的特殊限制:每位朋友不喜欢的菜品编号范围为一个区间,即对于每位客人 i,存在整数 l,r(l≤r),满足 ai,j=−1 当且仅当 j∈[l,r];
- 第 4 个子任务(40 分)没有特殊限制。
对于所有测试点,保证 n≤20,m≤106,ai,j≤109。
提示
一些测试点的输入规模较大,请注意程序的 IO 效率。