Module: Lặp qua hoán vị

Problem

Nhiều sinh viên sống trong ký túc xá. Ký túc xá — đó là một thế giới rộng lớn đầy niềm vui và cơ hội, nhưng nó cũng có mặt trái của nó.
Trong ký túc xá chỉ có một vòi hoa sen, và tất nhiên, có nhiều người muốn tắm vào buổi sáng hơn. Vì vậy, sáng nào cũng có năm người xếp hàng trước phòng tắm của ký túc xá.
Ngay khi vòi hoa sen mở ra, người đầu tiên xếp hàng bước vào vòi hoa sen. Sau một thời gian, khi người đầu tiên bước ra khỏi vòi hoa sen, người tiếp theo sẽ bước vào. Quá trình này tiếp tục cho đến khi mọi người trong hàng đợi đã tắm xong.

Vòi hoa sen — nó không phải là một công việc kinh doanh nhanh chóng, vì vậy trong khi chờ đợi, sinh viên giao tiếp. Tại mỗi thời điểm, học sinh giao tiếp theo cặp: (2i - 1)-người thứ trong hàng đợi (hiện tại) giao tiếp với (2i)-m.
Hãy xem xét quá trình này chi tiết hơn. Hãy biểu thị những người theo số từ 1 đến 5. Đặt hàng đợi ban đầu trông giống như 23154 (người 2 đứng đầu hàng đợi). Rồi trước khi khai hồn 2 thông với 3, 1 thông với 5, 4 không thông với ai. Rồi 2 đứa đi tắm. Trong khi 2 đang tắm, 3 và 1 trò chuyện, 5 và 4 trò chuyện. Rồi 3 vào tắm. Trong khi 3 đang tắm, 1 và 5 đang nói chuyện, 4 không nói chuyện với ai. Sau đó, 1 đi tắm, và trong khi anh ấy tắm, 5 và 4 giao tiếp với nhau. Sau đó, 5 người đi tắm và sau đó 4 người đi tắm.

Được biết, nếu học sinh i và j giao tiếp với nhau thì niềm vui của học sinh i tăng thêm g_{i, j} và niềm vui của học sinh j tăng thêm g_{j, i}. Bạn cần tìm thứ tự ban đầu của các học sinh trong hàng đợi sao cho tổng niềm vui của tất cả học sinh cuối cùng là lớn nhất. Điều đáng chú ý là một số sinh viên có thể giao tiếp nhiều lần. Trong ví dụ trên, học sinh lớp 1 và lớp 5 đang trò chuyện trong khi chờ vòi hoa sen mở và cả khi học sinh lớp 3 tắm.

Đầu vào:
Dữ liệu gồm năm dòng, mỗi dòng chứa năm số nguyên cách nhau bởi dấu cách: số thứ j trong dòng thứ i biểu thị g_{i, j} (0 ≤ g< sub >i, j ≤ 10⁵). Đảm bảo rằng g_{i, j} = 0 với mọi i.

Xét các học sinh được đánh số từ 1 đến 5.

Đầu ra:
In một số nguyên duy nhất — niềm vui tổng thể tối đa có thể của học sinh.

Ví dụ:
 

Đầu vào	Đầu ra
0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0	32
0 43 21 18 2 3 0 21 11 65 5 2 0 1 4 54 62 12 0 99 87 64 81 33 0	620