7753: BZOJ3753：Wall

众所周知，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 ，且至少一个权值非负，至少一个好网站。

题目来源

没有写明来源