/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2021/7/17 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
整数 N と、長さ N の整数列 A, B が与えられます。
高橋君にはこれからの N 日間で、以下のことが起こります。
- i 日目の朝 : 所持金が A_i 円増えます。
- i 日目の昼 : 自分の所持金が負とならないという条件の下、好きな金額を支払ってコンピュータを購入することが出来ます。 コンピュータを購入しないという選択をすることも可能です。既に別のコンピュータを所持している状態で新たなコンピュータを購入した場合、元のコンピュータは破棄されます。
- i 日目の夜 : 仕事をします。この仕事をこなすには、高橋君が価格が B_i 円以上のコンピュータを所持している必要があります。
はじめ、高橋君の所持金は 0 円であり、高橋君はコンピュータを所持していません。
高橋君が全ての仕事をこなすことが可能かどうかを判定してください。
可能な場合、 高橋君が全ての仕事をこなしたという条件の下での、N 日目終了時点での高橋君の所持金の最大値を答えてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
高橋君が全ての仕事をこなすことが可能な場合、高橋君が全ての仕事をこなしたという条件の下での、N 日目終了時点での高橋君の所持金の最大値を答えてください。
高橋君が全ての仕事をこなすことが不可能な場合、-1 を出力してください。
入力例 1
3 5 1 2 4 4 6
出力例 1
4
高橋君は、1 日目の昼に 1 円のコンピュータを購入、2 日目の昼に 6 円のコンピュータを購入し、 3 日目の昼にはコンピュータを購入しないという選択をすることで、 全ての仕事をこなした上で、 3 日目終了時点での所持金を 4 円にすることができます。
入力例 2
3 3 2 1 2 3 6
出力例 2
-1
高橋君は、どのような選択を行っても、全ての仕事をこなすことはできません。 よって、-1 を出力します。
Score : 6 points
Warning
Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
Given are an integer N and sequences A and B of N integers each.
For the next N days, the following will happen to Takahashi.
- On the morning of Day i: He gains A_i yen (Japanese currency).
- On the afternoon of Day i: He is given an opportunity to buy a computer by paying any amount of money he likes as long as it will not result in a negative cash balance. He is allowed to choose not to buy a computer. If a new computer is bought when he already has one, the old one will be thrown away.
- On the night of Day i: He does his job. To do it, he has to own a computer worth B_i yen or more.
Initially, Takahashi has zero yen and no computer.
Determine whether it is possible for Takahashi to do all the jobs.
If it is possible, find the maximum possible amount of money he has at the end of Day N on the condition that all jobs are done.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
If it is possible for Takahashi to do all the jobs, print the maximum possible amount of money he has at the end of Day N on the condition that all jobs are done.
If it is impossible for Takahashi to do all the jobs, print -1.
Sample Input 1
3 5 1 2 4 4 6
Sample Output 1
4
Takahashi can buy a computer worth 1 yen on the afternoon of Day 1, another worth 6 yen on Day 2, and nothing on Day 3 to do all the jobs and have 4 yen at the end of Day 3.
Sample Input 2
3 3 2 1 2 3 6
Sample Output 2
-1
Regardless of what choices Takahashi makes, he cannot do all the jobs. Thus, we should print -1.