在 N*M 的棋盘上互不覆盖地放置 1*2 和 2*1 的多米诺方块，有一些格子上有障碍，这些格子不能放置多米诺方块。在每个没有障碍的格子上有两个费用值，分别表示这个格子上横放和竖放多米诺方块所需的费用。试问存不存在一种放置多米诺的方案，能放满所有无障碍的格子。若存在，求出完成放置的最小费用；若不存在，求出最多能放置多少个多米诺。

数据规模

保证第一行的答案不超过 2^30。

对于 30% 的数据，N, M <= 5。

对于 80% 的数据，N, M 中至少有一个不超过8。

对于 100% 的数据，N, M <= 40。

备注

本题设有部分分，对于每种情况，如果你的程序只输出了第一行且答案正确，可以得到该测试点 70% 的分数。但是如果你的程序输出了放置方案而方案不正确，该测试点得0分。

[感谢题目作者wish]

第一行两个正整数 N 和 M，表示棋盘共 N 行 M 列。

后为两个 N*M 的矩阵，分别表示棋盘每个格子横放和竖放多米诺的费用。费用为正整数，若费用为0，则格子是障碍格（保证障碍格两个费用均为0）。

若存在至少一种放置方案，则第一行输出最小费用，后跟一个 N*M 的矩阵，表示最小费用方案。

若不存在满足要求的放置方案，则第一行输出最多能够放置多少个多米诺，后跟一个 N*M 的矩阵，输出一种放置方案。

方案可能有很多种，只需输出任意一种即可。

输出的方案中，0表示这个格子不放置多米诺，1表示这个格子的多米诺横放，2 表示这个格子的多米诺竖放。