#ABC340D. 最速通关
最速通关
题目描述
一款游戏共有 个关卡,编号为 ,最初只能游玩第 关。对于任意 ,当第 关可以游玩时,可以任选以下一种操作:
花费 秒通关第 关,解锁第 关;
花费 秒通关第 关,解锁第 关。
除通关耗时以外,其余时间忽略不计。求最早在多少秒后可以游玩第 关,不需要再通关第 关。
输入格式
第一行输入一个整数 。
此后 行,第 行输入三个整数 $a_i,b_i,x_i\left(1\leqq a_i,b_i\leqq10^9;\ 1\leqq x_i\leqq n\right)$。跳转目标可以是当前关卡,也可以是编号更小的关卡。
输出格式
输出一个整数,代表最早可以游玩第 关的时间。答案可能超过 位整数范围。
测试样例
5
100 200 3
50 10 1
100 200 5
150 1 2
350
样例 1 解释
先花 秒通过第 关,解锁第 关;再花 秒通过第 关,解锁第 关;最后花 秒通过第 关,解锁第 关。总时间为 秒,且不存在更快的方案。
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