You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

游戏 (games)

【题目描述】

小H最近迷上了一款游戏。

这个游戏由编号为 $1$,$2$,…,$N$ 的 $N$ 个关卡组成，你最开始在第$1$关的位置。

关卡十分困难，所以你通过关卡需要花费许多时间。

对于每个关卡 $i$ ($1\le i\le N-1$) ,你有两种通关方式：

• 花费 $A_i$ 分钟来通过关卡 $i$,这样你可以去往下一关 $i+1$。
• 花费 $B_i$ 分钟来通过关卡 $i$,这使你能够玩关卡 $X_i$ 。

忽略其他时间，请问最少需要多少分钟小H才可以玩到第 $N$ 关？

【输入格式】

第一行一个整数 $N$ 。

接下来一共 $N-1$ 行，每行输入三个整数，分别代表 $A_i$,$B_i$,$X_i$。

【输出格式】

输出仅一行一个整数，表示小H通关所需要的时间。

###【样例输入1】

5
100 200 3
50 10 1
100 200 5
150 1 2

【样例输出1】

350

【样例输入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

【数据范围】

对于30%的数据 $2 \le N \le 10^3$

对于100%的数据 $2 \le N \le 2 \times 10^5 ,1 \le A_i,B_i \le 10^9,1\le X_i\le N$

时间限制 $1s$

空间限制 $512MB$