#1653. [语言月赛 202403] 大西洋船王

[语言月赛 202403] 大西洋船王

题目描述

亚瑟目前有 nn 个任务需要完成,对于一个任务,他需要派遣 11 到 mm 条船(不能不派遣)。派遣一条船出一次任务的花费为 kk 元,第 ii 次任务派出 jj 条船可以获得 ai,ja_{i,j} 元。

请计算最优情况下亚瑟的收入,请注意这个值可能是负数。

输入格式

第一行输入三个整数 n,m,kn,m,k。
接下来 nn 行每行输入 mm 个整数,第 ii 行的第 jj 个数为 ai,ja_{i,j}。

输出格式

输出一行一个整数,表示最优情况下亚瑟的收入。

样例

2 3 6
12 11 19
16 17 18
16

题目来源:洛谷 B3947