QOJ.ac

QOJ

Time Limit: 2.5 s Memory Limit: 512 MB Total points: 100

# 8319. Emiya 家明天的饭

统计

Emiya 是个擅长做菜的高中生,他会做 $m$ 道不同的菜品。某天,Yaz、Zid 和他们的 $n$ 个朋友们到他家做客,Emiya 需要做一些菜来招待他们。

Yaz 和 Zid 什么都吃,但他们的朋友们有些挑食。具体来说,我们用整数 $a_{i,j}\geq -1$ 来表示第 $i$ 个朋友对第 $j$ 道菜品的态度:

  • 若 $a_{i,j}\geq 0$,则第 $i$ 位朋友不讨厌这道菜品,如果饭桌上有这道菜,且没有其他让这位朋友讨厌的菜品,那么他会给 Emiya 留下 $a_{i,j}$ 元红包以表赞许和感谢。
  • 若 $a_{i,j} = -1$,则第 $i$ 为朋友讨厌这道菜品,如果饭桌上有这道菜,那么这位朋友会非常生气,并直接离席而去。这意味着他将不会因为任何菜品留下红包。

Emiya 擅长做菜,却不擅长计算,请你帮助 Emiya 挑选若干道菜品,使得他收到的红包数额总和最大。方便起见,你只需要输出这个最大的总和即可。

输入格式

从标准输入读入数据。

第一行包含两个整数 $n,m$,意义见题目描述。

第 $2$ 到第 $n+1$ 行,每行包含 $m$ 个整数:其中第 $i+1$ 行的第 $j$ 个整数为 $a_{i,j}$,意义见题目描述。

保证 $n,m\geq 1$,保证 $a_{i,j} \geq -1$。

输出格式

输出到标准输出。

一行一个整数,表示红包金额的最大总和。

样例

输入

3 3
1 2 3
2 -1 100
100 10 -1

输出

113

解释

最优方案是制作第 $1$ 和第 $2$ 道菜。若如此做,虽然第 $2$ 位客人会生气地离席而去,但另两位客人留下的红包总金额是最大的。

样例二

见下载目录下的 ex_2.inex_2.ans

样例三

见下载目录下的 ex_3.inex_3.ans

子任务

本题设置 4 个子任务:

  • 第 1 个子任务(20 分)的特殊限制:$n\leq 10, m\leq 2000$;
  • 第 2 个子任务(20 分)的特殊限制:$n\leq 14$;
  • 第 3 个子任务(20 分)的特殊限制:每位朋友不喜欢的菜品编号范围为一个区间,即对于每位客人 $i$,存在整数 $l,r$($l\leq r$),满足 $a_{i,j} = -1$ 当且仅当 $j\in \left[l,r\right]$;
  • 第 4 个子任务(40 分)没有特殊限制。

对于所有测试点,保证 $n\leq 20$,$m\leq 10^6$,$a_{i,j}\leq 10^9$。

提示

一些测试点的输入规模较大,请注意程序的 IO 效率。