Problem
Yeni müzikalin galası için N kişi sıraya girdi ve her biri 1 bilet almak istiyor. Tüm kuyruk için yalnızca bir bilet gişesi çalışıyordu, bu nedenle bilet satışları çok yavaştı ve "misafir" getiriyordu. çaresizlik içinde sıralar. En zeki olanlar, kural olarak, bir kasiyerin tek elde birkaç bileti aynı biletlerin teker teker satıldığı duruma göre daha hızlı sattığını hemen fark etti.
Bu nedenle, ayakta duran birkaç kişinin, herkes için bilet alması için ilkine para vermesini önerdiler.
Ancak spekülatörlerle mücadele etmek için kasiyer kişi başı 3'ten fazla bilet satmadı, bu nedenle sadece arka arkaya 2 veya 3 kişi bu şekilde anlaşmaya varabildi.
Kasiyerin kuyruktaki i'inci kişiye bir bilet satmak için Ai saniye harcadığı ve Bi olduğu biliniyor. iki bilet , üç bilet satmak için saniye - Ci saniye. Tüm müşterilere hizmet sunulabilecek minimum süreyi hesaplayacak bir program yazın.
Birleşmiş insanlardan oluşan bir grup için biletlerin her zaman içlerinden ilki tarafından satın alındığına dikkat edin. Ayrıca kimse hızlanmak için fazladan bilet (yani kimsenin ihtiyacı olmayan biletler) almaz.
Giriş:
- ilk satır, N sayısını içerir - kuyruktaki alıcıların sayısı (\(1<=N<=5000\)) ;
- sırada Ai, Bi doğal sayılarının N üçlüsü gelir , Ci. Bu sayıların her biri 3600'ü geçmez. Sıradaki kişiler kasadan başlayarak numaralandırılır.
Çıktı: tek bir sayı yazdırın - tüm müşterilere hizmet sunulabilecek saniye cinsinden minimum süre.
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
5
5 10 15
2 10 15
5 5 5
20 20 1
20 1 1
|
12 |
| 2 |
2
3 4 5
1 1 1
|
4 |