Magic Slab

题号：NC23832
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

lililalala得到了一块魔法板，这块魔法板可以被看做大小为 $\ n \times n$ 的矩形，它含有 $\ n \times n$ 个单元格。

lililalala可以通过点亮这块魔法板的某些部分获得一定的能量值。

给定两个长度为 $\ n$ 的数列 $\ a$ 和 $\ b$ 以及一个 $\ n \times n$ 的矩阵 $\ c$ 。具体规则如下:

可以花费 $\ a_{i}$ 点能量点亮魔法板（从上往下，下同）的第 $\ i$ 行 $\ (1 \le i \le n)$ 。
可以花费 $\ b_{i}$ 点能量点亮魔法板（从左往右，下同）的第 $\ i$ 列 $\ (1 \le i \le n)$ 。
如果第 $\ i$ 行和第 $\ j$ 列同时被点亮，那么就认为第 $\ i$ 行的第 $\ j$ 个单元格被点亮，可以获得 $\ c_{ij}$ 点能量 $\ (1 \le i,j \le n)$ 。
此外魔法板有额外的关联奖励，每条关联奖励包含两个单元格，也就是说如果如果同时点亮了两个单元格且它们之间有关联奖励，那么就能额外获得一部分能量。

假设lililalala初始有足够多的能量，他想知道采取最优策略后他最多能赚取多少能量？(赚取的能量=获得的能量-消耗的能量)。

第一行两个整数--魔法板的大小和关联奖励的条数。
然后的行表示矩阵，行中的第行第个整数表示--点亮第行的第个单元格可以获得的能量。
然后的一行个整数--点亮行的花费。
然后的一行个整数--点亮列的花费。
然后的行每行五个整数--其中第行包含--同时点亮第行第列和第行第列的单元格可以获得点能量。

输出一行包含一个整数--lililalala最多能赚取的能量。

示例1

复制

复制

示例2

复制

复制