B - お菓子選びコンテスト 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は、お菓子屋さんで開催されている「お菓子選びコンテスト」に参加しています。

店内には N 個のお菓子が並んでおり、それぞれ 1 つずつしかありません。各お菓子 i（1 \leq i \leq N）には、お店が設定した基本の美味しさポイント T_i と、高橋君の好みに基づく補正値 C_i が決まっています。高橋君がお菓子 i を選んだときに得られる 満足度 は T_i + C_i です。

高橋君は、N 個のお菓子の中から ちょうど K 個 を選びます。同じお菓子を複数回選ぶことはできません。ちょうど K 個を選ぶ必要があるため、満足度が負であるお菓子を選ばざるを得ない場合もあります。

選んだ K 個のお菓子の満足度の合計を最大化するとき、その最大値を求めてください。

制約

  • 1 \leq K \leq N \leq 2 \times 10^5
  • 1 \leq T_i \leq 10^9
  • -10^9 \leq C_i \leq 10^9
  • 入力はすべて整数

入力

N K
T_1 C_1
T_2 C_2
\vdots
T_N C_N
  • 1 行目には、お菓子の個数を表す整数 N と、選ぶお菓子の個数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各お菓子の基本の美味しさポイントと好み補正値が与えられる。
  • 1 + i 行目（1 \leq i \leq N）には、お菓子 i の基本の美味しさポイント T_i と好み補正値 C_i が、スペース区切りで与えられる。

出力

N 個のお菓子の中からちょうど K 個を選んだときの、満足度の合計の最大値を整数として 1 行で出力せよ。

入力例 1

5 3
10 5
8 -2
15 0
7 3
12 1

出力例 1

43

入力例 2

8 4
100 50
200 -100
150 30
80 20
120 -10
90 40
170 -50
110 25

出力例 2

595

入力例 3

12 6
1000000000 -500000000
500000000 500000000
800000000 100000000
300000000 600000000
750000000 -200000000
600000000 300000000
450000000 400000000
900000000 -100000000
200000000 700000000
650000000 150000000
550000000 250000000
700000000 0

出力例 3

5450000000

Score : 300 pts

Problem Statement

Takahashi is participating in a "Candy Selection Contest" held at a candy shop.

There are N candies lined up in the shop, each available in only one piece. For each candy i (1 \leq i \leq N), there is a base tastiness point T_i set by the shop and an adjustment value C_i based on Takahashi's preferences. The satisfaction Takahashi gains from choosing candy i is T_i + C_i.

Takahashi will choose exactly K candies from the N candies. He cannot choose the same candy more than once. Since he must choose exactly K candies, he may be forced to choose candies with negative satisfaction.

Find the maximum possible total satisfaction when choosing K candies to maximize the sum of their satisfactions.

Constraints

  • 1 \leq K \leq N \leq 2 \times 10^5
  • 1 \leq T_i \leq 10^9
  • -10^9 \leq C_i \leq 10^9
  • All input values are integers

Input

N K
T_1 C_1
T_2 C_2
\vdots
T_N C_N
  • The first line contains an integer N representing the number of candies and an integer K representing the number of candies to choose, separated by a space.
  • From the 2nd line to the (N + 1)-th line, the base tastiness point and preference adjustment value for each candy are given.
  • The (1 + i)-th line (1 \leq i \leq N) contains the base tastiness point T_i and the preference adjustment value C_i of candy i, separated by a space.

Output

Output in a single line the maximum total satisfaction as an integer when choosing exactly K candies from the N candies.

Sample Input 1

5 3
10 5
8 -2
15 0
7 3
12 1

Sample Output 1

43

Sample Input 2

8 4
100 50
200 -100
150 30
80 20
120 -10
90 40
170 -50
110 25

Sample Output 2

595

Sample Input 3

12 6
1000000000 -500000000
500000000 500000000
800000000 100000000
300000000 600000000
750000000 -200000000
600000000 300000000
450000000 400000000
900000000 -100000000
200000000 700000000
650000000 150000000
550000000 250000000
700000000 0

Sample Output 3

5450000000