← 返回题目列表

AtCoder · awc0069_b

B. 糖果评选大赛

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

高桥正在参加在糖果店举办的“糖果选择大赛”。

有 N 糖果在商店里排列整齐,每种糖果只有一件。对于每一颗糖果 i (1 \leq i \leq N),有一个基本的美味点 T_i 由商店设置和调整值 C_i 基于高桥的喜好。的 满意 高桥通过选择糖果获得收益 i is T_i + C_i.

高桥会选择 正是 K 糖果来自 N 糖果。他不能多次选择同一种糖果。因为他必须准确选择 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
  • 第一行包含一个整数 N 代表糖果的数量和一个整数 K 代表要选择的糖果数量,以空格分隔。
  • 从第 2 行到 (N + 1)第行,给出了每种糖果的基本口味点和偏好调整值。
  • 的 (1 + i)- 第行 (1 \leq i \leq N) 包含基本美味点 T_i 和偏好调整值 C_i 糖果 i,用空格分隔。

输出

在单行中以整数形式输出精确选择时的最大总满意度 K 糖果来自 N 糖果。


示例输入 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