← 返回题目列表

Codeforces · 391/C2

C2. 锦标赛

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

该问题由三个子问题组成:解决子问题 C1,您将获得 4 分,解决子问题 C2,您将获得 4 分,解决子问题 C3,您将获得 8 分。

马纳奥决定追求战士的职业生涯。他决定从正在进行的锦标赛开始。在Manao加入之前,比赛有n名参赛者,编号从1到n。他们每个人都已经获得了一定的锦标赛积分,即第 i 个战士拥有 pi 积分。

Manao将与每位参赛者进行一场单打。马瑙的每一场战斗都以胜利或失败告终。一场胜利给予马瑙一分,而一场失败则给予马瑙对手一分。对于每个 i,Manao 估计了他需要投入多少努力 ei 才能击败第 i 名参赛者。输掉一场战斗并不需要任何努力。

马瑙完成所有战斗后,将确定排名,1为最好排名,n+1为最差排名。参赛者将按照比赛积分的降序排列。与马纳奥积分相同的选手,如果赢得了对他的比赛,排名就会比他高,否则排名会比他低。与其他战士打破联系的确切机制与此无关。

Manao的目标是达到k级或更高。如果可能的话,确定他为了实现这个目标需要投入的最小总努力量。

输入

第一行包含一对整数 n 和 k (1 ≤ k ≤ n + 1)。以下 n 行中的第 i 行包含由单个空格分隔的两个整数 — pi 和 ei (0 ≤ pi, ei ≤ 200000)。

该问题由三个子问题组成。子问题对输入有不同的约束。正确提交子问题将获得一些分数。子问题的描述如下。

- 在子问题 C1(4 点)中,约束 1 ≤ n ≤ 15 将成立。
- 在子问题 C2(4 点)中,约束 1 ≤ n ≤ 100 将成立。
- 在子问题 C3(8 点)中,约束 1 ≤ n ≤ 200000 将成立。

输出

在一行中打印一个数字——Manao 排名前 k 所需的最小努力。如果再多的努力也无法获得马瑙这样的排名,输出数字-1。

示例

输入 #1

3 2
1 1
1 4
2 2

输出 #1

3

输入 #2

2 1
3 2
4 0

输出 #2

-1

输入 #3

5 2
2 10
2 10
1 1
3 1
3 1

输出 #3

12

注意

考虑第一个测试用例。当马瑙参加比赛时,有三名战士。第一个拥有 1 个锦标赛积分,要战胜他需要 1 个单位的努力。第二名选手也有 1 个锦标赛积分,但马瑙需要 4 个单位的努力才能击败他。第三名选手得 2 分,战胜他需要马瑙 2 个单位的努力。马瑙的目标是进入前二。最佳决策是战胜战士1和战士3,之后马瑙、战士2和战士3都将获得2分。马瑙的排名将比战斗机 3 好,比战斗机 2 差,因此排名第二。

考虑第二个测试用例。即使马瑙战胜了两个对手,他仍然会排名第三。