#1525. 石像复苏

石像复苏

题目描述

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

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

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

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

输入格式

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

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

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

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

输出格式

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

样例

2 3
2 1 3
1 3 1
2 1
1 1 2
8

数据范围与提示

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