/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 233 点
問題文
高橋君はフリーマーケットに出店しようとしています。手元には N 個の商品があり、 i 番目の商品の販売価格は A_i 円です。
ただし、各商品を販売するためには、梱包や陳列などの準備が必要です。 i 番目の商品の準備コストは B_i 円です。
高橋君は N 個の商品の中からいくつかの商品を選んで販売することができます。1 つも選ばなくても構いません。各商品について販売するかしないかを独立に決められますが、同じ商品を複数回販売することはできません。
商品の集合 S を選んで販売したときの利益は次のように計算されます。
\text{利益} = \sum_{i \in S} A_i - \sum_{i \in S} B_i
なお、1 つも商品を選ばない場合の利益は 0 円です。
高橋君が得られる利益の最大値を求めてください。
制約
- 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
- 1 行目には、商品の個数を表す整数 N が与えられる。
- 続く N 行のうち i 行目 (1 \leq i \leq N) には、 i 番目の商品の販売価格 A_i と準備コスト B_i がスペース区切りで与えられる。
出力
利益の最大値を 1 行で出力せよ。
入力例 1
3 10 3 5 8 7 2
出力例 1
12
入力例 2
3 3 5 2 7 1 4
出力例 2
0
入力例 3
10 100 50 30 80 200 199 15 15 500 100 60 120 45 30 90 90 300 250 10 1000
出力例 3
516
入力例 4
20 1000000000 1 999999999 1000000000 500000000 400000000 300000000 300000001 750000000 250000000 100 200 999999999 999999998 123456789 987654321 800000000 100000000 450000000 450000000 600000000 500000000 50000000 90000000 1 1 700000000 650000000 350000000 400000000 200000000 100000000 888888888 111111111 10 10 500000000 500000001 999999999 2
出力例 4
4327777774
入力例 5
1 1 1000000000
出力例 5
0
Score : 233 pts
Problem Statement
Takahashi is planning to set up a booth at a flea market. He has N items on hand, and the selling price of the i-th item is A_i yen.
However, each item requires preparation such as packaging and display before it can be sold. The preparation cost of the i-th item is B_i yen.
Takahashi can choose some items from the N items to sell. He may choose not to sell any items at all. He can independently decide whether or not to sell each item, but he cannot sell the same item more than once.
When he chooses a set of items S to sell, the profit is calculated as follows:
\text{Profit} = \sum_{i \in S} A_i - \sum_{i \in S} B_i
If no items are chosen, the profit is 0 yen.
Find the maximum profit that Takahashi can obtain.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- All input values are integers.
Input
N A_1 B_1 A_2 B_2 \vdots A_N B_N
- The first line contains an integer N, representing the number of items.
- The i-th of the following N lines (1 \leq i \leq N) contains the selling price A_i and the preparation cost B_i of the i-th item, separated by a space.
Output
Print the maximum profit in a single line.
Sample Input 1
3 10 3 5 8 7 2
Sample Output 1
12
Sample Input 2
3 3 5 2 7 1 4
Sample Output 2
0
Sample Input 3
10 100 50 30 80 200 199 15 15 500 100 60 120 45 30 90 90 300 250 10 1000
Sample Output 3
516
Sample Input 4
20 1000000000 1 999999999 1000000000 500000000 400000000 300000000 300000001 750000000 250000000 100 200 999999999 999999998 123456789 987654321 800000000 100000000 450000000 450000000 600000000 500000000 50000000 90000000 1 1 700000000 650000000 350000000 400000000 200000000 100000000 888888888 111111111 10 10 500000000 500000001 999999999 2
Sample Output 4
4327777774
Sample Input 5
1 1 1000000000
Sample Output 5
0