Problem
Một dòng người N xếp hàng mua vé xem buổi ra mắt vở nhạc kịch mới, mỗi người muốn mua 1 vé. Chỉ có một phòng vé làm việc cho cả hàng đợi nên lượng vé bán ra rất chậm, ế khách xếp hàng trong tuyệt vọng. Những người thông minh nhất nhanh chóng nhận thấy rằng, theo quy luật, nhân viên thu ngân bán nhiều vé bằng một tay nhanh hơn so với khi bán từng vé giống nhau.
Vì vậy, họ đề nghị nhiều người đứng thành hàng đưa tiền cho người đầu tiên trong số họ để anh ta mua vé cho mọi người.
Tuy nhiên, để chống lại những kẻ đầu cơ, nhân viên thu ngân chỉ bán mỗi người không quá 3 vé nên chỉ có 2 hoặc 3 người liên tiếp đạt được thỏa thuận theo cách này.
Được biết, nhân viên thu ngân dành Ai giây để bán một vé cho người thứ i trong hàng đợi và Bi giây để bán hai vé , ba vé - Ci giây. Viết chương trình tính toán thời gian tối thiểu mà tất cả khách hàng có thể được phục vụ.
Lưu ý rằng vé cho một nhóm người thống nhất luôn được mua bởi người đầu tiên trong số họ. Ngoài ra, không ai mua thêm vé (tức là vé mà không ai cần) để tăng tốc độ.
Đầu vào:
- dòng đầu tiên chứa số N - số lượng người mua trong hàng đợi (\(1<=N<=5000\)) ;
- tiếp theo là N bộ ba số tự nhiên Ai, Bi , Ci. Mỗi số này không vượt quá 3600. Những người trong hàng đợi được đánh số bắt đầu từ nhân viên thu ngân.
Đầu ra: in ra một số duy nhất - thời gian tối thiểu tính bằng giây mà tất cả khách hàng có thể được phục vụ.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 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 |