Cho một bàn cờ vua 8 x 8, mỗi ô có một giá trị A[i][j] nhất định (0 ≤ A[i][j] ≤ 100) tương ứng với điểm số đạt được nếu như bạn đặt một quân cờ vào đó. Nhiệm vụ của bạn là đặt 8 quản hậu lên bàn cờ, sao cho không có 2 quân nào ăn nhau, và số điểm đạt được là lớn nhất.

Gồm 8 dòng, mỗi dòng gồm 8 số tương ứng với các số trên bàn cờ.

Ràng buộc: 1<=A[i][j]<=100

Đầu ra: In ra số điểm đạt được lớn nhất.

Input:

12 29 80 91 56 46 97 13
54 88 27 84 85 9 32 77
48 80 88 74 30 77 38 98
6 82 20 95 7 86 12 43
100 82 15 7 95 9 5 84
51 40 65 98 86 38 30 63
96 78 98 76 33 11 2 58
33 51 35 68 62 87 67 39

Output:

653