题目描述
高桥正在玩一个游戏。
这个游戏由编号为 1,2,…,N 的 N 个关卡组成。最初，只能玩第 1 关。
对于每个可以玩的关卡 i（1≤i≤N−1），你可以在关卡 i 执行以下两个操作之一：
花费 Ai秒来通关关卡 i 。这使你能够玩下一个关卡 i+1。
花费Bi秒来通关关卡 i 。这使你能够玩关卡Xi 。
忽略除了完成关卡所需时间之外的其他时间，最少需要多少秒才能玩到第 N 关？
这个游戏由编号为 1,2,…,N 的 N 个关卡组成。最初，只能玩第 1 关。
对于每个可以玩的关卡 i（1≤i≤N−1），你可以在关卡 i 执行以下两个操作之一：
花费 Ai秒来通关关卡 i 。这使你能够玩下一个关卡 i+1。
花费Bi秒来通关关卡 i 。这使你能够玩关卡Xi 。
忽略除了完成关卡所需时间之外的其他时间，最少需要多少秒才能玩到第 N 关？
输入
2 ≤ N ≤ 2× 105
1 ≤ Ai，Bi≤ 109
1≤Xi≤N
样例输入 Copy
5
100 200 3
50 10 1
100 200 5
150 1 2
样例输出 Copy
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
输出：
90
样例3：输入:
6
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
输出：
5000000000
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
输出：
90
样例3：输入:
6
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
输出：
5000000000