Giải bài trực tuyến

    Cờ vua (còn gọi là cờ quốc tế) là môn thể thao trí tuệ được giới trẻ Việt Nam yêu thích và cũng là môn thể thao mà Việt Nam có quyền tự hào vì những thành tích xuất sắc mà các đại kiện tướng quốc tế trẻ (cả nam và nữ) của chúng ta đã đạt được.

    Thuận vừa trúng thưởng trong một kỳ thi tìm hiểu về phong trào cờ vua do Liên đoàn cờ vua Việt Nam tổ chức. Ban tổ chức có một cách thức xác định trị giá giải thưởng đòi hỏi người trúng thưởng phải am hiểu về cờ vua, nếu muốn giá trị giải thưởng cao hơn. Người trúng thưởng cần đặt 4 quân cờ Hậu, Xe, Tượng, Mã lên bàn cờ. Phần thưởng thu được sẽ là tổng giá trị của các ô bị 4 quân cờ này khống chế.

    Bàn cờ vua là một hình vuông kích thước 8x8 gồm 8 hàng ngang đánh số từ 1-8 từ dưới lên và 8 cột dọc đánh số từ 1-8 từ trái qua phải. Ô nằm trên hàng i và cột j được kí hiệu là ô (i,j). Hậu, Xe, Tượng, Mã là 4 quân cờ mạnh nhất của cờ vua, khả năng khống chế của chúng được mô tả như sau :

- Hậu: tất cả các ô thuộc cùng hàng ngang, cột dọc và đường chéo

- Xe: tất cả các ô thuộc cùng hàng ngang, cột dọc

- Tượng: tất cả các ô thuộc cùng đường chéo

- Mã: tất cả các ô ở đỉnh dối diện trên đường chéo của hình chữ nhật kích thước 2 x 3

    Trên K ô của bàn cờ, Ban tổ chức (BTC) có ghi các giá trị thưởng. Các ô này tạm gọi là ô thưởng. Nhiệm vụ của Thuận là tìm 4 ô trống (không có ghi giá trị) để đặt 4 quân cờ Hậu, Xe, Tượng, Mã sao cho giá trị giải thưởng là lớn nhất. Sau khi Thuận đặt xong, BTC sẽ xác định những ô thưởng nào bị ít nhất một quân cờ khống chế. Giá trị giải thưởng là tổng giá trị của các ô này.

Input

• Dòng đầu tiên ghi số nguyên dương K (K <= 60).
• Dòng thứ i trong số K dòng tiếp theo ghi 3 số nguyên dương u_i,v_i,c_i cho biết ô (u_i,v_i) là ô thưởng với giá trị c_i (c_i < 10⁹).

Output

• Ghi ra một số nguyên duy nhất là giá trị phần thưởng tìm được. 

Example

Input:

11

1 3 10

1 7 10

1 8 10

2 2 25

2 3 10

3 2 10

3 5 10

6 1 10

8 1 11

8 3 10

8 7 10

Output:

126

Giải thích : Thuận đặt quân Hậu ở ô (7,2), quân Xe ở ô (6,7), quân Tượng ở ô (2,4) và quân Mã ở ô (1,1).