Graffiti

Sur le chemin que vous empruntez quotidiennement pour aller à l'école, il y a un long trottoir pavé par des blocs de béton. Le trottoir fait trois blocs de large et est assez long (il semble toujours plus long quand vous rentrez à la maison). Un jour, vous découvrez que de jeunes irresponsables ont tracé des graffitis sur tous ces blocs. En regardant de plus près, vous réalisez qu'il s'agit de graffitis mathématiques : chaque bloc de béton a été marqué avec un entier.

Cette fois, la curiosité ne vous emporte pas. Vous décidez plutôt de jouer à un jeu avec vos amis sur le chemin de l'école. Le jeu se joue comme suit :

• Vous commencez par vous placer juste avant le début du trottoir contenant les graffitis.
• Chaque pas le long du trottoir doit être exactement sur une position à cheval sur les coins de quatre blocs. En marchant sur un coin d'un bloc, vous gagnez des points. Le nombre de points que vous gagnez pour un pas donné est la somme des nombres se trouvant sur les quatre blocs sur lesquels vous avez marché.
• Vous ne pouvez pas marcher sur le coin d'un bloc sur lequel vous avez déjà mis le pied. Autrement dit, une fois que vous avez mis le pied sur un coin d'un bloc, vous ne pouvez marcher sur aucun autre coin de ce bloc.
• Le nombre total de points que vous gagnez est additionné et devient votre score final.

Par exemple, le trottoir ci-dessous fait trois blocs de large et sept blocs de long. Le meilleur score possible est 50, obtenu en marchant sur les coins indiqués.

(1+3+11+9) + (-2-10+8+17) + (-1+3+2+9) = 24+13+13 = 50

Notez que vous pouvez laisser un nombre quelconque de blocs entre vos pas et ainsi, si tous les blocs contiennent un nombre négatif de points, vous pouvez simplement choisir de ne marcher sur aucun bloc et garder un score de 0.

Après plusieurs jours à jouer à ce jeu avec vos amis et à perdre systématiquement, vous décidez d'utiliser votre ordinateur pour vous assurer le meilleur score. Votre objectif est de déterminer le meilleur score qui peut être obtenu sur un trottoir couvert de graffitis, étant donné la longueur du trottoir et le nombre indiqué sur chaque bloc.

• 2 <= L <= 500 000, où L est la longueur du trottoir.

Votre programme doit lire sur l'entrée standard. La première ligne de l'entrée doit contenir un simple entier L, la longueur du trottoir.

Les L lignes suivantes ont chacune la forme x y z, décrivant les nombres écrits sur chacun des trois blocs de la rangée décrite. Ces trois nombres sont donnés dans l'ordre de la gauche à la droite du trottoir (tel que vu par une personne qui y marche), et seront toujours des entiers entre -100,000 et 100,000, inclus.

Votre programme doit écrire une ligne sur la sortie standard. Cette ligne doit contenir un simple entier, donnant le plus grand score que vous pouvez atteindre en marchant le long du trottoir. On vous garantit que la réponse ne dépassera jamais 2,000,000,000.

7
7 1 11
6 3 9
-4 -2 8
-8 -10 17
5 4 -3
-1 2 0
3 9 -3

50