题目背景

题目描述

Hikari 酱正在玩一款叫 Miencroft 的游戏。

游戏规则如下：

• 有 $m$ 种方块，$n$ 天，第 $i$ 种方块挖掉的收益为 $v_i$，在第 $j$ 天的数量为 $c_{i,j}$。
• Hikari 每天最多挖掉 $k$ 个方块。

现在 Hikari 想要让自己 $n$ 天获得的收益最大，请你编程求出这个收益值。

输入格式

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

第二行，$m$ 个整数，第 $i$ 个整数代表 $v_i$，表示该种方块的价值。

以后 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个整数为 $c_{i,j}$，表示第 $i$ 天第 $j$ 种方块的数量。

输出格式

一行一个整数 $w$，表示 $n$ 天的最大收益。

输入输出样例 #1

输入 #1

5 7 3000
361 713 -89 542 1493
1010 568 84725 939 841
202 399 71616 822 83
981 11 9300 92 3
0 0 0 0 0
91831 19481 91841 17462 88119
47729 71829 83838 38472 0
81282 0 0 73263 0

输出 #1

11992086

说明/提示

保证 $1\le m,n,k \le {10}^{5}$，$-{10}^9\le v_i\le {10}^9$，$0\le c_{i,j}\le {10}^9$，$m\times n\le 2\times{10}^{5}$。