Problem
Ramai pelajar tinggal di asrama. Asrama — ia adalah dunia yang menyeronokkan dan peluang yang besar, tetapi ia mempunyai kelemahannya.
Hanya ada satu bilik mandi di asrama, dan sudah tentu, lebih ramai orang yang ingin mandi pada waktu pagi. Oleh itu, setiap pagi beratur lima orang di hadapan bilik mandi asrama.
Sebaik sahaja pancuran mandian dibuka, orang pertama dalam barisan memasuki bilik mandi. Selepas beberapa lama, apabila yang pertama keluar dari pancuran, yang seterusnya memasuki pancuran. Proses ini berterusan sehingga semua orang dalam barisan mandi.
Mandi — ia bukan perniagaan yang pantas, jadi sementara menunggu, pelajar berkomunikasi. Pada setiap saat, pelajar berkomunikasi secara berpasangan: (2i - 1)-orang ke dalam baris gilir (pada masa ini) berkomunikasi dengan (2i)-m.
Mari kita pertimbangkan proses ini dengan lebih terperinci. Mari kita nyatakan orang dengan nombor dari 1 hingga 5. Biarkan baris gilir pada mulanya kelihatan seperti 23154 (orang 2 berada di kepala baris gilir). Kemudian sebelum membuka jiwa 2 berkomunikasi dengan 3, 1 berkomunikasi dengan 5, 4 tidak berkomunikasi dengan sesiapa pun. Kemudian 2 pergi ke bilik mandi. Semasa 2 sedang mandi, 3 dan 1 sedang berbual, dan 5 dan 4 sedang berbual. Kemudian 3 masuk mandi. Semasa 3 sedang mandi, 1 dan 5 bercakap, 4 tidak bercakap dengan sesiapa. Kemudian 1 memasuki bilik mandi, dan semasa dia mandi, 5 dan 4 berkomunikasi. Kemudian 5 pergi ke bilik mandi dan kemudian 4 pergi ke bilik mandi.
Adalah diketahui bahawa jika pelajar i dan j berkomunikasi, maka kegembiraan pelajar i meningkat sebanyak g
i, j, dan kegembiraan pelajar j meningkat sebanyak g
j, i. Anda perlu mencari susunan awal pelajar dalam baris gilir sehingga jumlah kegembiraan semua pelajar pada akhirnya adalah maksimum. Perlu diingat bahawa sesetengah pelajar boleh berkomunikasi beberapa kali. Dalam contoh di atas, pelajar 1 dan 5 sedang berbual sambil menunggu pancuran mandian dibuka dan juga semasa 3 mandi.
Input:
Input terdiri daripada lima baris, setiap baris mengandungi lima integer yang dipisahkan ruang: nombor ke-j dalam baris ke-i menandakan g
i, j (0 ≤ g< sub >i, j ≤ 10
5). Ia dijamin bahawa g
i, j = 0 untuk semua i.
Pertimbangkan pelajar bernombor dari 1 hingga 5.
Output:
Cetak satu integer — jumlah kegembiraan maksimum yang mungkin bagi pelajar.
Contoh:
| Input |
Output |
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 |