题目描述

高桥君正在玩一款游戏。

这款游戏包含 $1,2,\ldots,N$ 共 $N$ 个编号的关卡，目前他只能游玩第 $1$ 关。

对于每个关卡 $i$（$1\leq i \leq N-1$），当可以游玩该关卡时，可以选择以下两种操作之一：

• 用 $A_i$ 秒通关第 $i$ 关，从而解锁第 $i+1$ 关。
• 用 $B_i$ 秒通关第 $i$ 关，从而解锁第 $X_i$ 关。

除了通关各关卡所需的时间外，其余时间可以忽略。请问，最早在多少秒后可以游玩第 $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

输出

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

说明/提示

限制条件

• $2\leq N\leq 2\times 10^5$
• $1\leq A_i, B_i\leq 10^9$
• $1\leq X_i\leq N$
• 所有输入均为整数

样例解释 1

按照如下方式操作，可以在 $350$ 秒后游玩第 $5$ 关：

• 用 $100$ 秒通关第 $1$ 关，解锁第 $2$ 关。
• 用 $50$ 秒通关第 $2$ 关，解锁第 $3$ 关。
• 用 $200$ 秒通关第 $3$ 关，解锁第 $5$ 关。

由 ChatGPT 4.1 翻译