AT_abc084_c [ABC084C] Special Trains

[problemUrl]: https://atcoder.jp/contests/abc084/tasks/abc084_c Atcoder国に、 $ 1 $ 本の東西方向に走る鉄道が完成しました。 この鉄道には $ N $ 個の駅があり、西から順に $ 1 $,$ 2 $,$ ... $,$ N $ の番号がついています。 明日、鉄道の開通式が開かれます。 この鉄道では、$ 1≦i≦N-1 $ を満たす全ての整数 $ i $ に対して、駅 $ i $ から駅 $ i+1 $ に、$ C_i $ 秒で向かう列車が運行されます。ただし、これら以外の列車は運行されません。 駅 $ i $ から駅 $ i+1 $ に移動する列車のうち最初の列車は、開通式開始 $ S_i $ 秒後に駅 $ i $ を発車し、その後は $ F_i $ 秒おきに駅 $ i $ を発車する列車があります。 また、$ S_i $ は $ F_i $ で割り切れることが保証されます。 つまり、$ A％B $ で $ A $ を $ B $ で割った余りを表すとき、$ S_i≦t $,$ t％F_i=0 $ を満たす全ての $ t $ に対してのみ、開通式開始 $ t $ 秒後に駅 $ i $ を出発し、開通式開始 $ t+C_i $ 秒後に駅 $ i+1 $ に到着する列車があります。 列車の乗り降りにかかる時間を考えないとき、全ての駅 $ i $ に対して、開通式開始時に駅 $ i $ にいる場合、駅 $ N $ に到着できるのは最も早くて開通式開始何秒後か、答えてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ C_1 $ $ S_1 $ $ F_1 $ $ : $ $ C_{N-1} $ $ S_{N-1} $ $ F_{N-1} $

$ i $ 行目 $ (1≦i≦N) $ に、開通式開始時に駅 $ i $ にいる場合、駅 $ N $ に到着できるのが最も早くて開通式開始 $ x $ 秒後のとき、$ x $ を出力せよ。

### 制約 - $ 1≦N≦500 $ - $ 1≦C_i≦100 $ - $ 1≦S_i≦10^5 $ - $ 1≦F_i≦100 $ - $ S_i％F_i=0 $ - 入力は全て整数 ### Sample Explanation 1 駅 $ 1 $ からは、以下のように移動します。 - 開通式開始 $ 5 $ 秒後に、駅 $ 2 $ に向かう列車に乗る。 - 開通式開始 $ 11 $ 秒後に、駅 $ 2 $ に到着する。 - 開通式開始 $ 11 $ 秒後に、駅 $ 3 $ に向かう列車に乗る。 - 開通式開始 $ 12 $ 秒後に、駅 $ 3 $ に到着する。 駅 $ 2 $ からは、以下のように移動します。 - 開通式開始 $ 10 $ 秒後に、駅 $ 3 $ に向かう列車に乗る。 - 開通式開始 $ 11 $ 秒後に、駅 $ 3 $ に到着する。 駅 $ 3 $ に対しても、$ 0 $ を出力しなければならないことに注意してください。