UOJ Logo

NOI.AC

1S 512MB
Statistics

生产零件

时间限制:1秒,内存限制:128MB 读入文件名:workers.in 输出文件名:workers.out

【题目描述】

零件工厂里有$n$个工人,编号$1$到$n$。

员工每天都要做零件,每人在每天有自己必做的零件,第$i$个人第$j$天要做$a_{i,j}$个零件。

除此以外,他们好胜心强,所以每天都会暗中观察编号在他前面的$k$个员工做的零件总数(不包括他自己,不足$k$个的取前面的所有员工),第二天他就会额外多做这么多数量的零件。

第一天每个人只做自己必做数量的零件。

问第$m$天工作最多的一个员工做了多少零件。

【输入格式】

输入共$n+1$行。

第一行包含三个正整数$n$、$k$、$m$,分别表示工人人数、暗中观察员工数、工作天数,输入用一个空格分隔。

接下来$n$行每行有$m$个数,第$i$行的第$j$个数表示第$i$个员工在第$j$天固定要做的零件数量$a_{i,j}$,输入用一个空格分隔。

【输出格式】

输出共一行,包含一个正整数,表示第$m$天工作最多的员工做了多少零件。

结果可能很大,请对$1000000007$($1e9+7$)取模。

【输入输出样例1】

workers.in

4 2 3

1 1 10

2 1 9

1 1 8

2 2 1

workers.out

11

【输入输出样例2】

workers.in

5 3 4

6 10 1 9

3 2 9 1

4 4 4 10

7 9 7 5

9 2 10 8

workers.out

87

【数据规模与约定】

对于前30%的数据,$1≤n≤100$,$k=1$,$1≤a_{i,j}≤100$;

对于前60%的数据,$1≤n≤1000$,$1≤k≤10$;

对于100%的数据,$1≤n≤10000$,$1≤k≤n$,$1≤m≤10$,$1≤a_{i,j}≤10^9$;

【样例1解释】

第一天,四个员工分别做了1、2、1、2个零件。

第二天,四个员工分别做了1、1+1=2、3+1=4、3+2=5个零件。

第三天,四个员工分别做了10、1+9=10、3+8=11、6+1=7个零件。