题目描述
首先介绍一下Kakuro(カックロ) 这个游戏。
游戏规则为：
• 方形空格中填入1 ~ 9 的整数。
• 被斜线分开的方格中，右上角的数字等于其右侧邻接之连续方格
中数字之和，左下角的数字等于其下方邻接之连续方格中数字之
和。
• 无论是横向还是纵向，连续方格中的数字不能重复。
左边为一个Kakuro 游戏，右边为这个游戏的唯一解。
我们称一开始给出的数字为线索，称需要填入数字的地方为空格。如
果一个格子包含线索那么就不需要填入数字。我们约定所有的谜题都非空，
即至少有一个空格需要被填入。
注意：在以下题目中的游戏规则可能会有所不同，请认真阅读在每个
题目下的规则。
--------------------------------------------------------------------------------------------------------------------------------
输入
输出
输出一个整数表示答案。
样例输入
Copy
8 8 9 24
0 2 2 3 16
0 2 6 8 24
0 3 2 3 17
0 3 5 8 29
0 4 2 6 35
0 5 3 4 7
0 5 6 7 8
0 6 4 8 16
0 7 2 5 21
0 7 7 8 5
0 8 2 4 6
0 8 7 8 3
1 2 2 4 23
1 2 7 8 11
1 3 2 5 30
1 3 7 8 10
1 4 4 8 15
1 5 3 4 17
1 5 6 7 7
1 6 2 6 27
1 7 2 3 12
1 7 5 8 12
1 8 2 3 16
1 8 6 8 7
样例输出 Copy
127
提示
// 下面为这个样例的解释。
-1 -1 -1 -1 -1 -1 -1 -1
-1 1 2 -1 -1 3 3 2
-1 2 2 -1 2 4 4 2
-1 3 4 1 2 5 -1 -1
-1 -1 1 5 -1 6 5 -1
-1 -1 -1 4 5 5 5 3
-1 8 8 5 6 -1 4 3
-1 2 3 3 -1 -1 2 2
对于10% 的数据，保证n;m <= 3。
对于30% 的数据，保证n;m <= 50。对于50% 的数据，保证n;m <= 500。
对于另外20% 的数据，保证只有第一行第一列包含线索，剩下的地方全都是空格。
对于100% 的数据，保证3 <= n; m; T <= 10^5; 1 <= k <= 10^5; s <= 10^18。