Description

Input

第一行给出数字N,M代表行列数.N,M均小于等于100 下面N行M列用于描述数字矩阵

Output

输出最多可以拿到多少块宝石

Sample Input

1
2
3

2 2
1 2
2 1

Sample Output

1

4

Source

2007Amber国家队论文

Solution

黑白染色后最大权闭合子图。

胡波涛论文上的题目。大致题意是选了一个数就不能选相邻格子里面的数字。黑白染色后S->Black流量为权值，Black->White_Adjacent_To_Black流量为inf，White->T流量为权值。