题目描述

大西洋船王 Arthur von Montgomery 是 ScaredQiu 的童年男神。

亚瑟目前有 $n$ 个任务需要完成，对于一个任务，他需要派遣 $1$ 到 $m$ 条船（不能不派遣）。派遣一条船出一次任务的花费为 $k$ 元，第 $i$ 次任务派出 $j$ 条船可以获得 $a_{i,j}$ 元。

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

输入格式

第一行输入三个整数 $n,m,k$。

接下来 $n$ 行每行输入 $m$ 个整数，第 $i$ 行的第 $j$ 个数为 $a_{i,j}$。

输出格式

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

样例 #1

样例输入 #1

2 3 6
12 11 19
16 17 18

样例输出 #1

16

提示

样例解释

任务 1 派 $1$ 条船，收益 $12-6=6$；任务 2 派 $1$ 条船，收益 $16-6=10$，合计 $16$。

数据规模与约定

• 对于 $20\%$ 的数据，$1\leq n,m\leq 8$；
• 对于 $50\%$ 的数据，$1\leq n,m\leq 100$；
• 对于 $100\%$ 的数据，$1\leq n,m\leq 1000$，输入的所有数字都为整数，且都不超过 C++ 中 $32$ 位有符号整数可表示的范围。