AT_abc340_d [ABC340D] Super Takahashi Bros.

[problemUrl]: https://atcoder.jp/contests/abc340/tasks/abc340_d 高橋君はゲームをプレイしています。 ゲームは $ 1,2,\ldots,N $ の番号がついた $ N $ 個のステージからなり、現在はステージ $ 1 $ のみを遊ぶことができます。 各ステージ $ i $ ( $ 1\leq\ i\ \leq\ N-1 $ )が遊べるとき、ステージ $ i $ では以下の $ 2 $ つのどちらかの行動を行えます。 - $ 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} $

答えを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ 1\ \leq\ A_i,\ B_i\ \leq\ 10^9 $ - $ 1\ \leq\ X_i\ \leq\ N $ - 入力は全て整数 ### Sample Explanation 1 次のように行動することで、$ 350 $ 秒でステージ $ 5 $ を遊べるようになります。 - $ 100 $ 秒掛けてステージ $ 1 $ をクリアし、ステージ $ 2 $ を遊べるようになる。 - $ 50 $ 秒掛けてステージ $ 2 $ をクリアし、ステージ $ 3 $ を遊べるようになる。 - $ 200 $ 秒掛けてステージ $ 3 $ をクリアし、ステージ $ 5 $ を遊べるようになる。