Có \(n\) mảnh nhựa hình vuông đơn vị, các mảnh nhựa được đánh số từ \(1\) đến \(n\). Trên mỗi cạnh và ở tâm hình vuông của mảnh nhựa ghi một số nguyên không âm. Mảnh nhựa được phép xoay nhưng không được lật.

Nhiệm vụ của người chơi là lựa chọn các mảnh nhựa và xếp thành một dãy thỏa mãn điều kiện sau:

• Hai mảnh nhựa kề cạnh nhau thì số ghi trên hai cạnh tiếp xúc đó phải bằng nhau;
• Tổng các số ở tâm các mảnh nhựa xếp được là lớn nhất.

Input

• Dòng đầu chứa số nguyên \(n\);
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa năm số nguyên không âm \(a_i, b_i, c_i, d_i, w_i\) (\(0 \le a_i, b_i, c_i, d_i \le 3\)) mô tả các số trên bốn cạnh hình vuông theo chiều kim đồng hồ và số \(w_i\) là số ở tâm của mảnh nhựa thứ \(i\).

Output

• Ghi một số nguyên \(S\) là tổng các số ở tâm các mảnh nhựa xếp được lớn nhất.

Example

5
1 2 1 2 1
1 2 1 2 1
1 2 1 2 1
3 0 3 0 1
3 3 3 3 1

3

Ràng buộc

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 10\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 20\).
• Subtask \(3\) (\(50\%\) số điểm): \(n \le 100\); \(a_i = b_i; c_i = d_i\).