AT_abc341_b [ABC341B] Foreign Exchange

[problemUrl]: https://atcoder.jp/contests/abc341/tasks/abc341_b $ 1 $ から $ N $ までの番号がつけられた $ N $ 個の国があり、$ i\ =\ 1,\ 2,\ \ldots,\ N $ について、高橋君は国 $ i $ の通貨を $ A_i $ 単位持っています。 高橋君は、下記の操作を好きな回数（ $ 0 $ 回でも良い）繰り返します。 - まず、$ 1 $ 以上 $ N-1 $ 以下の整数 $ i $ を選ぶ。 - その後、国 $ i $ の通貨を $ S_i $ 単位以上持っているなら、下記の行動を $ 1 $ 回行う。 - 国 $ i $ の通貨を $ S_i $ 単位だけ支払い、国 $ (i+1) $ の通貨を $ T_i $ 単位だけ獲得する。 最終的に高橋君が持っている国 $ N $ の通貨の単位数としてあり得る最大値を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ S_1 $ $ T_1 $ $ S_2 $ $ T_2 $ $ \vdots $ $ S_{N-1} $ $ T_{N-1} $

答えを出力せよ。

### 制約 - 入力される値はすべて整数 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ A_i\ \leq\ 10^9 $ - $ 1\ \leq\ T_i\ \leq\ S_i\ \leq\ 10^9 $ ### Sample Explanation 1 以下の説明では、高橋君が持っている各国の通貨の単位数を、数列 $ A\ =\ (A_1,\ A_2,\ A_3,\ A_4) $ として表します。はじめ、$ A\ =\ (5,\ 7,\ 0,\ 3) $ です。 下記の通りに $ 4 $ 回操作を行うことを考えます。 - $ i\ =\ 2 $ を選び、国 $ 2 $ の通貨 $ 4 $ 単位を支払って、国 $ 3 $ の通貨 $ 3 $ 単位を獲得する。その結果、$ A\ =\ (5,\ 3,\ 3,\ 3) $ となる。 - $ i\ =\ 1 $ を選び、国 $ 1 $ の通貨 $ 2 $ 単位を支払って、国 $ 2 $ の通貨 $ 2 $ 単位を獲得する。その結果、$ A\ =\ (3,\ 5,\ 3,\ 3) $ となる。 - $ i\ =\ 2 $ を選び、国 $ 2 $ の通貨 $ 4 $ 単位を支払って、国 $ 3 $ の通貨 $ 3 $ 単位を獲得する。その結果、$ A\ =\ (3,\ 1,\ 6,\ 3) $ となる。 - $ i\ =\ 3 $ を選び、国 $ 3 $ の通貨 $ 5 $ 単位を支払って、国 $ 4 $ の通貨 $ 2 $ 単位を獲得する。その結果、$ A\ =\ (3,\ 1,\ 1,\ 5) $ となる。 このとき、最終的に高橋君が持っている国 $ 4 $ の通貨の単位数は $ 5 $ であり、これが考えられる最大値です。