CF391C3.The Tournament

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.

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.

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.

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.