Problem
一行 N 人排队购买新音乐剧首映式的门票，每人想买一张票。整个队列只有一个售票处，所以售票非常缓慢，带来了“客人”绝望地排队。最聪明的人很快就注意到，通常情况下，收银员一只手卖出多张票比一次卖出一张相同的票要快。
因此，他们建议站成一排的几个站着的人给第一个站着的人钱，让他给大家买票。
但收银员为了打击投机者，每人卖出的票数不超过3张，因此只能连续2、3人以这种方式达成协议。
已知收银员花费 Ai 秒将一张票卖给队列中的第 i 人，并且 Bi秒卖两张票，三张票 - 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 |