分数: 425 点
问题陈述
高桥正在玩游戏。
游戏包括 N 阶段编号 1,2,\ldots,N。最初只是阶段性的 可以播放 1 。
对于每个阶段 i ( 1\leq i \leq N-1 )可以播放,您可以在舞台上执行以下两个操作之一 i:
- 花费 A_i 秒数通关 i。这可以让你玩舞台 i+1.
- 花费 B_i 秒数通关 i。这可以让你玩舞台 X_i.
不考虑通关时间以外的时间,最少需要多少秒才能玩完关卡 N?
约束
- 2 \leq N \leq 2\times 10^5
- 1 \leq A_i, B_i \leq 10^9
- 1 \leq X_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
A_1 B_1 X_1
A_2 B_2 X_2
\vdots
A_{N-1} B_{N-1} X_{N-1}
输出
打印答案。
示例输入 1
5 100 200 3 50 10 1 100 200 5 150 1 2
示例输出 1
350
通过执行以下操作,您将被允许上台 5 in 350 秒。
- 花费 100 秒数通关 1,允许您玩舞台 2.
- 花费 50 秒数通关 2,允许您玩舞台 3.
- 花费 200 秒数通关 3,允许您玩舞台 5.
示例输入 2
10 1000 10 9 1000 10 10 1000 10 2 1000 10 3 1000 10 4 1000 10 5 1000 10 6 1000 10 7 1000 10 8
示例输出 2
90
示例输入 3
6 1000000000 1000000000 1 1000000000 1000000000 1 1000000000 1000000000 1 1000000000 1000000000 1 1000000000 1000000000 1
示例输出 3
5000000000