#3753. Wall

内存限制:256 MiB 时间限制:20 Sec

题目描述

众所周知,GFW的出现促进了社会的和谐。Wayne于是想研究一下GFW。
Wayne喜欢网格,所以他把一些网站排成了N_ M的网格,每个格子代表一个网站。每个网
站有一个评分,当然评分可正可负。现在Wayne想用一堵“墙”围住一些网站,使得评分和最大。
所谓“墙”,就是一个由网格的边组成的简单多边形,不能自交,也不能有空洞。
过了一会儿Wayne发现这个模型太一般了。出于一些原因,有些网站必须在“墙”外,我们称之
为“坏网站”;而有些网站必须在“墙”内,我们称之为“好网站”。当然了,“坏网站”的评分不一定
低,“好网站”的评分不一定高。Wayne又想知道,这种情况下,能够得到的最大评分和。注意,并
不总是存在合法的方案,所以当无法实现时,输出“Can not establish GFW.”。

输入格式

第一行两个正整数N和M。
接下来N行,每行M个用空格隔开的整数,表示网站的权值。
最后N行,每行M个用空格隔开的整数,1 表示坏网站,2 表示好网站,0 表示其他网站。

输出格式

输出两行,第一行一个整数表示一堵“墙”能围住的最大评分和,第二行表示有限制时的答案。

样例

样例输入


			
3 3
2 -1 2
-3 100 -3
-3 20 -3
2 0 2
0 1 0
0 0 0

样例输出


			
123
17

数据范围与提示

对于 100% 的数据,N<=10,M<=10,权值的绝对值不超过 10^6 ,且至少一个权值非负,至少一个好网站。