‎۳‎ تعمیرکار ماشین در مرکز ‎«بهینه‌سازی مصرف سوخت‎» کار می‌کنند. این ‎۳‎ تعمیرکار ‎$W_2$‎، ‎$W_1$‎ و ‎$W_3$‎ نام دارند.

امروز صبح، در جلوی این‌مرکز، ‎$n$‎ خودروی سواری صف کشیده‌اند تا به‌ترتیب موتورشان تنظیم شود. می‌دانیم تنظیم‌کردن موتور هر خودرو برای هر یک از ‎۳‎ تعمیرکار همواره دقیقاً یک دقیقه طول می‌کشد منتهی دستمزدی که تعمیرکار ‎$W_i$‎ برای تنظیم خودروی ‎$C_j$‎ دریافت می‌کند برای ‎$i$ها و ‎$j$های مختلف متفاوت بوده و در یک جدول داده شده است.

نکته‌ی جالب این مرکز، رابطه‌ی حسادت (یا به‌عبارت بهتر تنبلی) میان تعمیرکارهاست‎!‎ بدین صورت که تعمیرکار $W_i$ ($1\le i \le 3$)‎ تنها در صورتی (در ابتدای یک دقیقه) حاضر می‌شود موتور یک خودرو را تعمیر کند که تعمیرکارهای با اندیس کم‌تر (در صورت وجود) نیز در آن دقیقه مشغول باشند. به‌عنوان مثال امکان ندارد که در یک دقیقه فقط تعمیرکارهای ‎$W_1$‎ و ‎$W_3$‎ مشغول کار باشند؛ چرا که شرط کار کردن تعمیرکار ‎$W_3$‎، فعّال بودن هر دوی ‎$W_1$‎ و ‎$W_2$‎ است.

هم‌چنین برای احترام صف و رعایت ترتیب حضور و قرارگیری خودروها در صف، برای هر دو خودروی ‎$C_i$‎ و ‎$C_j$ (که ‎$1 \le i \le j \le n$‎)، موتور خودروی ‎$C_i$‎ باید همواره در زمانی زودتر‎‎ یا همزمان با موتور خودروی ‎$C_j$‎ تنظیم شود. به‌عبارت دیگر، در ابتدای هر دقیقه، ‎$1\le k\le 3$‎ خودرو از ابتدای صف وارد مرکز شده و (با چینشی که ما تعیین می‌کنیم) توسّط تعمیرکارهای اوّل تا ‎$k$‎اُم در یک دقیقه موتورشان تنظیم می‌شود.

با این وصف، از شما خواسته شده تا برنامه‌ای بنویسید که برنامه‌ریزی مناسبی برای کارکردن تعمیرکارها و انتساب خودروها به آن‌ها ارائه کند تا با دریافت کم‌ترین دستمزد (و نه لزوماً در کوتاه‌ترین زمان) موتور تمام ‎$n$‎ خودرو تنظیم شود. دقّت کنید که زمان پایان تمام کارها می‌تواند بین ‎$\lceil \frac{n}{3} \rceil$‎ و ‎$n$‎ دقیقه باشد و اصلاً هم برای ما اهمّیّتی ندارد‎!‎

• در سطر اوّل ورودی، ‎$n$‎، تعداد ماشین‌های حاضر در صف آمده است.
• در ‎$n$‎ سطر بعدی (سطرهای ‎$2 \le i \le n+1$‎ ورودی)، در سطر ‎$i$،‎اُم، ‎۳‎ عدد آمده است که به‌ترتیب (از چپ به راست) دست‌مزد دریافتی تعمیرکار اوّل، دوم و سوم برای تنظیم موتور خودروی ‎«$i-1$»‎اُم است.
• فرض کنید خودروها به‌ترتیب قرارگیری‌شان در صف در ورودی آمده‌اند و اوّلین خودرو در صف‎(که الزاماً در اوّلین دقیقه وارد مرکز می‌شود ولی الزاماً توسط تعمیرکار اوّل تنظیم نمی‌شود‎!‎) خودرویی است که دست‌مزدهای آن در سطر دوم ورودی نوشته شده است.
• ‎$0 \le n \le 2\times10^5$‎ و تمام دست‌مزدها صحیح، مثبت و کوچک‌تر از ‎$2\times10^5$‎ هستند.

در تنها سطر خروجی کم‌ترین دست‌مزد دریافتی توسّط تعمیرکارها برای تنظیم موتورهای ‎$n$‎ خودروی ورودی را بنویسید.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل