分数: 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