测试数据来自 system/3001

作业已超过截止时间，您无法递交本题目。

最优数独

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　数独游戏在一个9*9的方格中有一些格子中上已经填有1~9的数字，玩家需要把剩余的方格中也填上1~9的数字，使得方格的每一行，每一列中包含1~9这九个数字；同时保证，空格中用粗线划分的9个3*3的方格也同时包含1~9这九个数字。
　　　　　
　　作为数独游戏的升级版，每个方格还有额外的一个参数，并规定玩家最后得分是每个格子的参数与数字乘积的和，要求玩家最后的得分尽量高才算赢。

【输入格式】

　　开始的9行，每行包含9个整数（每个数都在1~20的范围内），表示数独各方格得参数。
　　接下来的9行，每行包含9个整数（每个数都在0~9的范围内），表示一个尚未填满的数独方格，空格用“0”表示。
　　每两个数字之间用一个空格隔开。

【输出格式】

　　输出可以得到的数独游戏的最高分数。如果这个数独无解，则输出整数-1。

【输入输出样例1】

　Input

3 2 1 5 6 8 2 4 7
6 1 8 2 9 3 5 1 9 
3 5 7 2 9 2 1 7 4
5 3 7 2 8 1 6 4 3
9 2 6 1 9 3 2 5 2
5 2 8 6 2 1 8 2 3
7 2 5 1 8 2 6 3 4
4 5 2 9 1 7 3 2 7
1 3 5 6 3 2 5 9 2
7 0 0 9 0 0 0 0 1
1 0 0 0 0 5 9 0 0
0 0 0 2 0 0 0 8 0
0 0 5 0 2 0 0 0 3
0 0 0 0 0 0 6 4 8
4 1 3 0 0 0 0 0 0
0 0 7 0 0 2 0 9 0
2 0 1 0 6 0 8 0 4
0 8 0 5 0 4 0 1 2 

　Output

1799

【输入输出样例2】

　Input

6 6 6 6 6 6 6 6 6
6 7 7 7 7 7 7 7 6
6 7 8 8 8 8 8 7 6
6 7 8 9 9 9 8 7 6
6 7 8 9 10 9 8 7 6
6 7 8 9 9 9 8 7 6
6 7 8 8 8 8 8 7 6
6 7 7 7 7 7 7 7 6
6 6 6 6 6 6 6 6 6
0 0 0 7 0 2 4 5 3
9 0 0 0 0 8 0 0 0
7 4 0 0 0 5 0 1 0
1 9 5 0 8 0 0 0 0
0 7 0 0 0 0 0 2 5
0 3 0 5 7 9 1 0 8
0 0 0 6 0 1 0 0 0
0 6 0 9 0 0 0 0 1
0 0 0 0 0 0 0 0 6

　Output

2852

【来源】

　　Mr.he