Description

最近小煜煜和小赫赫迷上了数独，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向毛哥请教，毛哥拿出了他最近发明的数独，作为这两个孩子笔试的题目。

数独的规则是这样的，在9×9的大九宫格中有9个3×3的小九宫格。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入1到9的数字。每个数字在每个小九宫格内都不能重复出现，每个数字在每行、每列也不能重复出现。但是由于一股神秘的力量，在每一个方格里都有一个分值。

毛哥要求每个人必须完成一个给定的数独（每个给定的数独有可能有不同的填法），并且要争取更高的总分数。而这个总分数即为每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图所示，在下面这个已经完成的数独里，总分为737分。

由于小赫赫要陪女朋友，所以他找到了善于编程的你，让你帮他求出，对于给定的数独，能够得到的最高分数。

Input

一共9行，每行9个整数（取值从0到9），其中0表示未填的空格。每两个数字之间用一个空格隔开。

Output

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

Sample Input 1

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

Sample Input 2

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

Sample Output 1

743

其中一个最大解为

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

Sample Output 2

697

其中一个最大解为

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

数据范围

40%的数据，数独中非0数的个数不少于30
80%的数据，数独中非0数的个数不少于26
100%的数据，数独中非0数的个数不少于24

Hint

请先尝试找出数独的所有解，再比较分数大小