Module: Eindimensionale Dynamik

Für die Tickets für die Premiere des neuen Musicals hat sich eine Schlange von N gebildet, von denen jeder ein Ticket kaufen möchte. Es funktionierte nur eine Kasse für die ganze Reihe, daher ging der Ticketverkauf sehr langsam und brachte die "Gäste" der Warteschlange in Verzweiflung. Die klügsten bemerkten schnell, dass der Kassierer in der Regel mehrere Tickets in einer Hand schneller verkauft, als wenn dieselben Tickets einzeln verkauft werden. 

Deshalb boten sie mehreren aufeinanderfolgenden Personen an, dass sie dem ersten von ihnen Geld geben sollten, damit er überhaupt Tickets kaufte. 

 

Um Spekulanten zu bekämpfen, verkaufte die Kassiererin jedoch nicht mehr als 3 Tickets in einer Hand, so dass nur 2 oder 3 aufeinanderfolgende Personen auf diese Weise miteinander verhandeln konnten.

 

Es ist bekannt, dass für den Verkauf von i an eine Person in der Warteschlange mit einem Ticket der Kassierer Ai Sekunden ausgibt, für den Verkauf von zwei Tickets Bi Sekunden, für drei Tickets Ci Sekunden. Schreiben Sie ein Programm, das die minimale Zeit berechnet, in der alle Käufer bedient werden konnten.

 

Bitte beachten Sie, dass die Eintrittskarten für eine Gruppe von Personen, die sich zusammengeschlossen haben, immer das erste von ihnen kaufen. Auch kauft niemand, um es zu beschleunigen, zusätzliche Tickets (dh Tickets, die niemand benötigt).

 

Eingabe: 
- die Zahl N ist in der ersten Zeile geschrieben - die Anzahl der Käufer in der Warteschlange (\(1<=N<=5000\));
- als nächstes kommen N drei natürliche Zahlen Ai, Bi, Ci. Jede dieser Zahlen überschreitet 3.600 nicht. Die Personen in der Warteschlange sind nummeriert, beginnend an der Kasse.

 

Ausgabe: Geben Sie eine einzige Zahl aus - die minimale Zeit in Sekunden, für die alle Käufer bedient werden konnten.