电力的价格会根据供求关系而波动。作为一家 24 小时运转的零件生产工厂的经理，Homer 希望能够最小化运营工厂的能源成本。Homer 无法控制电价，也无法改变生产零件所需的能源量。然而，工厂安装了一些太阳能电池板，可以将阳光转化为电能。Homer 正在考虑购买一个容量为 $B$ 兆瓦时（MWh）的蓄电池，以便将能量储存起来供以后使用。他想知道这样的购买在经济上是否合理。

利用过去的数据，Homer 预测了未来 $N$ 个小时（以下 $1 \le i \le N$）的如下信息：

• $p_i$：第 $i$ 个小时的能源价格（单位：美元/MWh）
• $r_i$：第 $i$ 个小时运营工厂所需的能源量（单位：MWh）
• $s_i$：第 $i$ 个小时太阳能电池板产生的能源量（单位：MWh）

此外，Homer 假设蓄电池初始时是空的。

在每个小时，Homer 可以决定采取以下一种或多种行动，以满足该小时的能源需求：

• 使用一定量产生的太阳能
• 使用一定量蓄电池中储存的能量
• 从电力公司购买能源，每购买 1 MWh 支付 $p_i$ 美元

在满足了该小时的能源需求后，Homer 还可以选择采取以下一种或多种行动：

• 将一部分多余的能量（由多余的太阳能、多余的购买能源和已储存的电池能量组合而成）存入蓄电池中，最多不超过蓄电池的容量。
• 出售一部分多余的能量。每个小时，电力公司提供 $M$ 个能源回购计划。对于第 $j$ 个回购计划，Homer 可以以 $c_{i,j}$ 美元的价格恰好出售 $d_{i,j}$ MWh 的能量。每个小时最多只能选择一个回购计划。
• 浪费掉一部分多余的能量。

请帮助 Homer 确定未来 $N$ 个小时运营工厂的最小成本。在第 $N$ 个小时结束时，蓄电池中剩余的任何能量都将被视为浪费。负的成本意味着 Homer 可以获利。

输入格式

第一行包含三个整数 $N$（$1 \le N \le 1\,000$）、$M$（$1 \le M \le 10$）和 $B$（$1 \le B \le 20$），其中 $N$ 是小时数，$M$ 是每小时可用的回购计划数量，$B$ 是蓄电池的容量。

接下来的 $N$ 行，每行包含三个整数 $p_i$、$r_i$ 和 $s_i$（$1 \le p_i, r_i, s_i \le 100$），其中 $p_i$ 是第 $i$ 个小时的能源价格，$r_i$ 是第 $i$ 个小时运营工厂所需的能源量，$s_i$ 是第 $i$ 个小时产生的太阳能。

接下来的 $N$ 行，每行包含 $M$ 个整数，满足 $1 \le c_{i,j} \le 10\,000$，其中 $c_{i,j}$ 是第 $i$ 个小时第 $j$ 个回购计划的价格。

接下来的 $N$ 行，每行包含 $M$ 个整数，满足 $1 \le d_{i,j} \le 100$，其中 $d_{i,j}$ 是第 $i$ 个小时第 $j$ 个回购计划可以出售的能源量（单位：MWh）。

输出格式

输出未来 $N$ 个小时运营工厂所需的最小成本。

样例

输入样例 1

2 1 10
4 3 3
1 5 3
4
9
2
3

输出样例 1

-4

输入样例 2

3 4 5
1 5 3
9 4 3
10 6 3
1 3 4 9
1 3 6 9
1 3 6 30
1 2 3 4
1 2 3 4
1 2 3 4

输出样例 2

1

输入样例 3

3 2 2
1 3 6
4 6 3
10 6 3
4 10
2 9
10 20
1 10
2 4
1 3

输出样例 3

18