AT_past202107_o コンピュータ

[problemUrl]: https://atcoder.jp/contests/past202107-open/tasks/past202107_o 整数 $ N $ と、長さ $ N $ の整数列 $ A $, $ B $ が与えられます。 高橋君にはこれからの $ N $ 日間で、以下のことが起こります。 - $ i $ 日目の朝 : 所持金が $ A_i $ 円増えます。 - $ i $ 日目の昼 : 自分の所持金が負とならないという条件の下、好きな金額を支払ってコンピュータを購入することが出来ます。 コンピュータを購入しないという選択をすることも可能です。既に別のコンピュータを所持している状態で新たなコンピュータを購入した場合、元のコンピュータは破棄されます。 - $ i $ 日目の夜 : 仕事をします。この仕事をこなすには、高橋君が価格が $ B_i $ 円以上のコンピュータを所持している必要があります。 はじめ、高橋君の所持金は $ 0 $ 円であり、高橋君はコンピュータを所持していません。 高橋君が全ての仕事をこなすことが可能かどうかを判定してください。 可能な場合、 高橋君が全ての仕事をこなしたという条件の下での、$ N $ 日目終了時点での高橋君の所持金の最大値を答えてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_N $ $ B_N $

高橋君が全ての仕事をこなすことが可能な場合、高橋君が全ての仕事をこなしたという条件の下での、$ N $ 日目終了時点での高橋君の所持金の最大値を答えてください。 高橋君が全ての仕事をこなすことが不可能な場合、$ -1 $ を出力してください。

### 注意 この問題に対する言及は、2021/7/17 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - $ 1\ \leq\ B_i\ \leq\ 10^9 $ - 入力はすべて整数である。 ### Sample Explanation 1 高橋君は、$ 1 $ 日目の昼に $ 1 $ 円のコンピュータを購入、$ 2 $ 日目の昼に $ 6 $ 円のコンピュータを購入し、 $ 3 $ 日目の昼にはコンピュータを購入しないという選択をすることで、 全ての仕事をこなした上で、 $ 3 $ 日目終了時点での所持金を $ 4 $ 円にすることができます。 ### Sample Explanation 2 高橋君は、どのような選択を行っても、全ての仕事をこなすことはできません。 よって、$ -1 $ を出力します。