#6707. 石像复苏

内存限制:128 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: SilveryStar

题目描述

「那一天,世界上所有的人类都……变成了石头! 」

せんくう作为第一个在石之世界复苏的人,成功的用酒精和硝酸制作出了奇迹之水,现在せんくう想复活一个 n\times m 的矩阵里的石像,但是奇迹之水有限,对于第 i 行的石像,せんくう准备了 x_i 份奇迹之水,对于第 j 列的石像,也只能使用 y_j 份奇迹之水,奇迹之水可以不使用完,且只能用在对应的行/列上

せんくう发现矩阵中的任意一个石像 (i,\,j) 都需要两份奇迹之水才能复活,也就是 x_i y_j 各消耗一份

每个石像复苏后都会为科学帝国带来更多的劳动力,せんくう根据这些人的体格给他们定义了一个能力值 w(i,\,j) ,现在せんくう想知道怎样使用奇迹之水能给科学帝国带来尽可能多的实力

输入格式

第一行两个整数 n,\,m ,表示石像矩阵有 n m

下面 n 行,每行 m 个整数,表示石像矩阵的能力值 w(i,\,j)

n+2 行有 n 个整数,表示每一行能用的奇迹之水的数量 x_i

n+3 行有 m 个整数,表示每一列能用的奇迹之水的数量 y_j

输出格式

输出包含一个整数,表示科学帝国能得到的最大能力值

样例

样例输入

2 3
2 1 3
1 3 1
2 1
1 1 2

样例输出

8

数据范围与提示

对于 100\% 的数据,保证 n,m\le100