2514 - 靶形数独

通过次数

0

提交次数

0

Time Limit : 1 秒
Memory Limit : 128 MB

小城和小华都是热爱数学的好学生,最近,他们不约而同地迷上了数独游戏,好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了,于是他们向Z博士请教。Z博士拿出了他最近发明的“靶形数独”,作为这两个盖子比试的题目。

靶形数独的方格同普通数独一样,在9格宽*9格高的大九宫格中有9个3格宽*3格高的小九宫格(用粗黑色线隔开)。在这个大九宫格中,有一些数字是已知的,根据这些数字,利用逻辑推理,在其他的空格里填入1到9的数字。每个数字在每个小九宫格内不能重复出现,每个数字在每行灭了也不能重复出现,每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同,即每一个方格都有一个分值,而且如同一个靶子一样,离中心越近则分值越高。如图1-3-7所示。

15654215951263.png

图1-3-7具体的分值分布是:最里面一格(黄色区域)为10分,黄色区域外面的一圈(红色区域)  每个格子为9分,再外面一圈(蓝色区域)每个格子为8分,蓝色区域外面一圈(棕色区域)每个格子为7分,最外面一圈(白色区域)每个格子为6分,如图1-3-7所示。比赛要求是:每个人必须完成一个给定的数独(每个给定的数独有可能有不同的填法),而且要争取最高的总分。总分是每个方格上的分值和这个数独相应格上的数字的乘积的总和。如图1-3-8所示,在以下这个已经填好的靶形数独中,总分为2829。游戏规定以总分的高低决出胜负。

15654216596520.png

由于求胜心切,小城找到了善于编程的你,让你帮他求出对于给定的靶形数独能够得到的最高分数。

Input

输入文件名为sudoku.in。

一共9行,每行9个整数(每个数都在0-9的范围内),表示一个尚未填满的数独方格,未填满的空格用“0”表示。每两个数字之间用一个空格隔开。

Output

输出文件sudoku.out,共1行。

输出可以得到的靶形数独的最高分。如果这个数独无解,则输出整数-1。

Examples

Input

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

2829

Input

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

Hint

40%的数据,数独中非0的个数不少于30。

80%的数据,数独中非0的个数不少于26。

100%的数据,数独中非0的个数不少于24。

Source

一本通提高