/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は果物屋を経営しています。
店には N 種類の果物がそれぞれ 1 個ずつあり、i 番目の果物（1 \leq i \leq N）には仕入れ値 C_i と売値 P_i が設定されています。高橋君はこの中からいくつかの果物を選んで本日のおすすめコーナーに並べたいと考えています。各果物は選ぶか選ばないかのいずれかであり、少なくとも 1 個は選ばなければなりません。
しかし、おすすめコーナーに並べる果物の価格帯があまりにもバラバラだと、お客さんが混乱してしまいます。そこで、選んだ果物の売値の最大値と最小値の差が D 以下でなければなりません。ここで D は入力で与えられる非負整数です。なお、果物を 1 個だけ選んだ場合、売値の最大値と最小値は等しいため差は 0 となり、この条件を必ず満たします。
各果物の利益は、売値から仕入れ値を引いた値 P_i - C_i で定まります。利益は負になることもあります。
高橋君は、上の条件を満たすように果物を選んだとき、選んだ果物の利益の合計を最大化したいと考えています。すべての果物の利益が負であっても、少なくとも 1 個は選ばなければならないことに注意してください。
利益の合計の最大値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq D \leq 10^9
- 1 \leq C_i \leq 10^9
- 1 \leq P_i \leq 10^9
- 入力はすべて整数である。
入力
N D C_1 P_1 C_2 P_2 \vdots C_N P_N
- 1 行目には、果物の種類数を表す整数 N と、売値の最大値と最小値の差の上限を表す整数 D が、スペース区切りで与えられる。
- 1 + i 行目（1 \leq i \leq N）には、i 番目の果物の仕入れ値 C_i と売値 P_i が、スペース区切りで与えられる。
出力
条件を満たすように 1 個以上の果物を選んだときの、利益の合計の最大値を 1 行で出力せよ。答えが負になる場合もあることに注意せよ。
入力例 1
4 3 3 5 4 7 10 9 2 12
出力例 1
10
入力例 2
3 10 10 5 8 6 20 13
出力例 2
-2
入力例 3
10 5 8 10 5 12 20 15 1 17 9 20 25 22 7 23 30 26 10 27 15 30
出力例 3
33
入力例 4
25 100 1000 500 100 550 200 610 800 650 300 700 900 720 150 760 500 790 400 810 1200 850 350 900 600 940 100 980 1100 1020 700 1050 200 1100 1300 1150 250 1190 800 1230 300 1280 900 1320 100 1360 1500 1400 500 1450 200 1500
出力例 4
2660
入力例 5
1 0 1000000000 1
出力例 5
-999999999
Score : 400 pts
Problem Statement
Takahashi runs a fruit shop.
The shop has N types of fruits, one of each, and the i-th fruit (1 \leq i \leq N) has a cost price C_i and a selling price P_i. Takahashi wants to select some of these fruits to display in today's recommended section. Each fruit is either selected or not selected, and at least 1 fruit must be selected.
However, if the price range of the fruits displayed in the recommended section varies too much, customers will be confused. Therefore, the difference between the maximum and minimum selling prices among the selected fruits must be at most D, where D is a non-negative integer given in the input. Note that if only 1 fruit is selected, the maximum and minimum selling prices are equal, so the difference is 0, and this condition is always satisfied.
The profit of each fruit is determined by the selling price minus the cost price, P_i - C_i. The profit can be negative.
Takahashi wants to maximize the total profit of the selected fruits while satisfying the above condition. Note that even if the profit of every fruit is negative, at least 1 fruit must be selected.
Find the maximum total profit.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq D \leq 10^9
- 1 \leq C_i \leq 10^9
- 1 \leq P_i \leq 10^9
- All inputs are integers.
Input
N D C_1 P_1 C_2 P_2 \vdots C_N P_N
- The first line contains an integer N representing the number of types of fruits and an integer D representing the upper limit of the difference between the maximum and minimum selling prices, separated by a space.
- The (1 + i)-th line (1 \leq i \leq N) contains the cost price C_i and selling price P_i of the i-th fruit, separated by a space.
Output
Print in one line the maximum total profit when selecting 1 or more fruits while satisfying the condition. Note that the answer may be negative.
Sample Input 1
4 3 3 5 4 7 10 9 2 12
Sample Output 1
10
Sample Input 2
3 10 10 5 8 6 20 13
Sample Output 2
-2
Sample Input 3
10 5 8 10 5 12 20 15 1 17 9 20 25 22 7 23 30 26 10 27 15 30
Sample Output 3
33
Sample Input 4
25 100 1000 500 100 550 200 610 800 650 300 700 900 720 150 760 500 790 400 810 1200 850 350 900 600 940 100 980 1100 1020 700 1050 200 1100 1300 1150 250 1190 800 1230 300 1280 900 1320 100 1360 1500 1400 500 1450 200 1500
Sample Output 4
2660
Sample Input 5
1 0 1000000000 1
Sample Output 5
-999999999