CF391C2.The Tournament

This problem consists of three subproblems: for solving subproblem C1 you will receive 4 points, for solving subproblem C2 you will receive 4 points, and for solving subproblem C3 you will receive 8 points.

Manao decided to pursue a fighter's career. He decided to begin with an ongoing tournament. Before Manao joined, there were n contestants in the tournament, numbered from 1 to n. Each of them had already obtained some amount of tournament points, namely the i-th fighter had p__i points.

Manao is going to engage in a single fight against each contestant. Each of Manao's fights ends in either a win or a loss. A win grants Manao one point, and a loss grants Manao's opponent one point. For each i, Manao estimated the amount of effort e__i he needs to invest to win against the i-th contestant. Losing a fight costs no effort.

After Manao finishes all of his fights, the ranklist will be determined, with 1 being the best rank and n + 1 being the worst. The contestants will be ranked in descending order of their tournament points. The contestants with the same number of points as Manao will be ranked better than him if they won the match against him and worse otherwise. The exact mechanism of breaking ties for other fighters is not relevant here.

Manao's objective is to have rank k or better. Determine the minimum total amount of effort he needs to invest in order to fulfill this goal, if it is possible.

本题包含三个子问题：解决子问题 C1 可得 4 分，解决子问题 C2 可得 4 分，解决子问题 C3 可得 8 分。

马瑙决定投身格斗家事业。他决定从一场正在进行的锦标赛入手。在马瑙加入之前，锦标赛中已有 $n$ 名选手，编号为 $1$ 至 $n$。每位选手已获得一定数量的锦标赛积分，其中第 $i$ 位选手拥有 $p_i$ 分。

马瑙将与每位现有选手各进行一场比赛。马瑙的每场比赛结果非胜即负：获胜可为马瑙赢得 1 分；失败则为其对手赢得 1 分。对每个 $i$，马瑙预估了自己战胜第 $i$ 位选手所需付出的努力值 $e_i$；而输掉一场比赛则无需付出任何努力。

在马瑙完成全部比赛后，将根据积分确定最终排名，其中第 $1$ 名为最佳，第 $n+1$ 名为最差。选手按其锦标赛积分降序排列。若某位选手积分与马瑙相同，则当该选手曾击败马瑙时，其排名优于马瑙；否则排名劣于马瑙。其余选手之间平分情况的具体排名规则在此问题中无关紧要。

马瑙的目标是获得第 $k$ 名或更优的排名。请判断：若可行，马瑙为达成此目标所需的最小总努力值是多少？

The first line contains a pair of integers n and k (1 ≤ k ≤ n + 1). The i-th of the following n lines contains two integers separated by a single space — p__i and e__i (0 ≤ p__i, e__i ≤ 200000).

The problem consists of three subproblems. The subproblems have different constraints on the input. You will get some score for the correct submission of the subproblem. The description of the subproblems follows.

• In subproblem C1 (4 points), the constraint 1 ≤ n ≤ 15 will hold.
• In subproblem C2 (4 points), the constraint 1 ≤ n ≤ 100 will hold.
• In subproblem C3 (8 points), the constraint 1 ≤ n ≤ 200000 will hold.

第一行包含一对整数 $n$ 和 $k$（$1 \leq k \leq n + 1$）。接下来的 $n$ 行中，第 $i$ 行包含两个由单个空格分隔的整数——$p_i$ 和 $e_i$（$0 \leq p_i, e_i \leq 200000$）。

本题包含三个子问题。各子问题对输入的约束条件不同。正确提交每个子问题可获得相应分数。各子问题的描述如下：

• 子问题 C1（4 分）：满足约束 $1 \leq n \leq 15$；
• 子问题 C2（4 分）：满足约束 $1 \leq n \leq 100$；
• 子问题 C3（8 分）：满足约束 $1 \leq n \leq 200000$。

Print a single number in a single line — the minimum amount of effort Manao needs to use to rank in the top k. If no amount of effort can earn Manao such a rank, output number -1.

在单独一行中输出一个整数——Manao 要进入前 $k$ 名所需的最小努力值。如果无论付出多少努力都无法使 Manao 进入前 $k$ 名，则输出数字 $-1$。

Consider the first test case. At the time when Manao joins the tournament, there are three fighters. The first of them has 1 tournament point and the victory against him requires 1 unit of effort. The second contestant also has 1 tournament point, but Manao needs 4 units of effort to defeat him. The third contestant has 2 points and victory against him costs Manao 2 units of effort. Manao's goal is top be in top 2. The optimal decision is to win against fighters 1 and 3, after which Manao, fighter 2, and fighter 3 will all have 2 points. Manao will rank better than fighter 3 and worse than fighter 2, thus finishing in second place.

Consider the second test case. Even if Manao wins against both opponents, he will still rank third.

考虑第一个测试用例。当马瑙加入锦标赛时，共有三名选手。其中第一名选手有 1 个锦标赛积分，击败他需要花费 1 单位努力值；第二名选手也有 1 个锦标赛积分，但马瑙击败他需要花费 4 单位努力值；第三名选手有 2 个积分，击败他需花费马瑙 2 单位努力值。马瑙的目标是进入前两名。最优策略是击败第 1 号和第 3 号选手：此后，马瑙、第 2 号选手与第 3 号选手的积分均为 2。马瑙的排名将优于第 3 号选手、劣于第 2 号选手，因此最终位列第二。

考虑第二个测试用例。即使马瑙击败了两名对手，他仍将排在第三名。