Super Takahashi Bros.

题目描述

Takahashi 正在玩一个游戏。 游戏由编号为 $1,2,\ldots,N$ 的 $N$ 个关卡组成。最开始，只有关卡 $1$ 可以玩。 对于每个可以玩的关卡 $i$（$1\leq i \leq N-1$），你可以在关卡 $i$ 处执行以下两种动作之一：

花费 $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}$

输出格式

输出答案。

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

350

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

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$ 所有输入值均为整数。按照如下操作，你将能够在 $350$ 秒内玩到关卡 $5$。

花费 $100$ 秒来通关关卡 $1$，这将允许你玩关卡 $2$。 花费 $50$ 秒来通关关卡 $2$，这将允许你玩关卡 $3$。 花费 $200$ 秒来通关关卡 $3$，这将允许你玩关卡 $5$。

标签: AtCoder|abc340D

来源

AtCoder|abc340D