Problem
Barisan N orang berbaris untuk tiket ke tayangan perdana muzikal baharu, yang masing-masing mahu membeli 1 tiket. Hanya satu pejabat tiket berfungsi untuk keseluruhan baris gilir, jadi penjualan tiket sangat perlahan, membawa "tetamu" beratur dalam keadaan terdesak. Mereka yang paling bijak dengan cepat menyedari bahawa, sebagai peraturan, juruwang menjual beberapa tiket dalam satu tangan lebih cepat daripada apabila tiket yang sama dijual satu demi satu.
Oleh itu, mereka mencadangkan beberapa orang berdiri berturut-turut memberi wang kepada yang pertama daripada mereka supaya dia membeli tiket untuk semua orang.
Namun, untuk melawan spekulator, juruwang menjual tidak lebih daripada 3 tiket bagi setiap orang, jadi hanya 2 atau 3 orang berturut-turut boleh mencapai persetujuan dengan cara ini.
Adalah diketahui bahawa juruwang meluangkan masa Ai untuk menjual satu tiket kepada iorang ke- dalam baris gilir dan Bi saat untuk menjual dua tiket , tiga tiket - Ci saat. Tulis program yang akan mengira masa minimum yang semua pelanggan boleh dilayan.
Perhatikan bahawa tiket untuk sekumpulan orang bersatu sentiasa dibeli oleh yang pertama daripada mereka. Selain itu, tiada siapa yang membeli tiket tambahan (iaitu tiket yang tiada siapa perlukan) untuk mempercepatkan.
Input:
- baris pertama mengandungi nombor N - bilangan pembeli dalam baris gilir (\(1<=N<=5000\)) ;
- seterusnya ialah N tiga kali ganda nombor asli Ai, Bi , Ci. Setiap nombor ini tidak melebihi 3600. Orang dalam baris gilir diberi nombor bermula dari juruwang.
Output: cetak satu nombor - masa minimum dalam saat yang semua pelanggan boleh dilayan.
Contoh
| # |
Input |
Output |
| 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 |