Problem
Beaucoup d'étudiants vivent dans une auberge. Auberge — c'est un vaste monde de plaisir et d'opportunités, mais il a ses inconvénients.
Il n'y a qu'une seule douche dans l'auberge, et bien sûr, il y a plus de gens qui veulent prendre une douche le matin. Par conséquent, chaque matin, il y a une file d'attente de cinq personnes devant la douche du dortoir.
Dès que la douche s'ouvre, la première personne en file entre dans la douche. Au bout d'un moment, quand le premier sort de la douche, le suivant entre dans la douche. Ce processus se poursuit jusqu'à ce que tout le monde dans la file d'attente ait pris une douche.
Douche & mdash; ce n'est pas une entreprise rapide, alors en attendant, les étudiants communiquent. À chaque instant, les élèves communiquent par paires : (2i - 1)-ième personne dans la file d'attente communique (actuellement) avec (2i)-m.
Considérons ce processus plus en détail. Désignons les personnes par des nombres de 1 à 5. Laissez la file d'attente ressembler initialement à 23154 (la personne 2 est en tête de file). Alors avant d'ouvrir l'âme 2 communique avec 3, 1 communique avec 5, 4 ne communique avec personne. Puis 2 va dans la douche. Pendant que 2 prend sa douche, 3 et 1 discutent, et 5 et 4 discutent. Puis 3 entre dans la douche. Pendant que 3 se douche, 1 et 5 parlent, 4 ne parle à personne. Puis 1 entre dans la douche, et pendant qu'il prend sa douche, 5 et 4 communiquent. Ensuite 5 va dans la douche puis 4 va dans la douche.
On sait que si les élèves i et j communiquent, alors la joie de l'élève i augmente de g
i, j, et la joie de l'élève j augmente de g
j, i. Vous devez trouver un tel ordre initial d'étudiants dans la file d'attente que la joie totale de tous les étudiants à la fin soit maximale. Il est à noter que certains élèves peuvent communiquer plusieurs fois. Dans l'exemple ci-dessus, les élèves 1 et 5 discutent en attendant que la douche s'ouvre et aussi pendant que 3 prend une douche.
Saisie :
L'entrée se compose de cinq lignes, chaque ligne contient cinq entiers séparés par des espaces : le jème nombre dans la ième ligne indique g
i, j (0 ≤ g< sous >i, j ≤ 10
5). Il est garanti que g
i, j = 0 pour tout i.
Considérez les élèves numérotés de 1 à 5.
Sortie :
Imprimer un seul entier — la joie totale maximale possible des étudiants.
Exemples :
| Entrée |
Sortie |
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 |