Module: Dynamique unidimensionnelle

Une file de N personnes fait la queue pour des billets pour la première de la nouvelle comédie musicale, chacune voulant acheter 1 billet. Une seule billetterie fonctionnait pour toute la file d'attente, donc les ventes de billets étaient très lentes, amenant des "invités" files d'attente en désespoir de cause. Les plus malins ont vite remarqué qu'en règle générale, un caissier vend plusieurs tickets d'une main plus rapidement que lorsque les mêmes tickets sont vendus un par un. 

Par conséquent, ils ont suggéré que plusieurs personnes debout à la suite donnent de l'argent au premier d'entre eux afin qu'il achète des billets pour tout le monde. 

 

Cependant, afin de lutter contre les spéculateurs, le caissier ne vendait pas plus de 3 billets par personne, donc seulement 2 ou 3 personnes d'affilée pouvaient parvenir à un accord de cette manière.

 

On sait que le caissier passe Ai secondes pour vendre un ticket à la i-ième personne dans la file d'attente, et Bi secondes pour vendre deux billets, trois billets - Ci secondes. Écrivez un programme qui calculera le temps minimum pendant lequel tous les clients pourraient être servis.

 

Notez que les billets pour un groupe de personnes solidaires sont toujours achetés par le premier d'entre eux. De plus, personne n'achète de billets supplémentaires (c'est-à-dire des billets dont personne n'a besoin) pour accélérer.

 

Entrée : 
- la première ligne contient le nombre N - le nombre d'acheteurs dans la file d'attente (\(1<=N<=5000\)) ;
- vient ensuite N triplets d'entiers naturels Ai, Bi , Ci. Chacun de ces nombres ne dépasse pas 3600. Les personnes dans la file d'attente sont numérotées à partir du caissier.

 

Résultat : imprimer un seul numéro - le temps minimum en secondes pendant lequel tous les clients pourraient être servis.