Problem
صفی از N برای تهیه بلیت برای اولین نمایش موزیکال جدید صف کشیده اند که هر کدام می خواهند 1 بلیط بخرند. فقط یک دفتر فروش بلیط برای کل صف کار می کرد، بنابراین فروش بلیط بسیار کند بود و "مهمان" می آورد. صف در ناامیدی باهوش‌ترین‌ها به سرعت متوجه شدند که به‌عنوان یک قاعده، یک صندوقدار چند بلیط را در یک دست سریع‌تر از زمانی که همان بلیت‌ها در یک زمان فروخته می‌شود، می‌فروشد.
بنابراین پیشنهاد کردند که چند نفر پشت سر هم ایستاده به نفر اول پول بدهند تا برای همه بلیط بخرد.
اما برای مبارزه با دلالان، صندوقدار برای هر نفر بیش از 3 بلیط فروخت، بنابراین فقط 2 یا 3 نفر پشت سر هم می توانستند از این طریق به توافق برسند.
مشخص است که صندوقدار برای فروش یک بلیط به i-امین نفر در صف و Bi، Ai را چند ثانیه صرف می کند. ثانیه برای فروش دو بلیط، سه بلیط - Ci ثانیه. برنامه ای بنویسید که حداقل زمان ارائه خدمات به همه مشتریان را محاسبه کند.
توجه داشته باشید که بلیط های گروهی از افراد متحد همیشه توسط اولین آنها خریداری می شود. همچنین، هیچ کس برای افزایش سرعت، بلیط اضافی نمی‌خرد (یعنی بلیط‌هایی که هیچ‌کس به آنها نیاز ندارد).
ورودی:
- خط اول شامل شماره N است - تعداد خریداران در صف (\(1<=N<=5000\)) ;
- بعدی N سه برابر اعداد طبیعی Ai، Bi می آید , Ci. هر یک از این اعداد از 3600 تجاوز نمی کند. افراد در صف از صندوقدار شماره گذاری می شوند.
خروجی: چاپ یک عدد - حداقل زمانی در ثانیه که می‌توان به همه مشتریان خدمات رسانی کرد.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 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 |