hunterxhunter

Time limit: 2s Memory limit: 256MB Input: Output:

In the first arc of the popular manga Hunter x Hunter the protagonist Gon and his friends take part in the Hunter Exam. In its fourth phase each of the NN participants gets a badge with a unique number between 00 and N1N - 1. Also, NN pieces of paper each with a unique number between 00 and N1N - 1 are put in a bowl. Each participant ii draws a piece of paper from the bowl (and doesn't return it); the piece of paper he gets shows the number TiT_{i} of his target. It is known that nobody drew their own number, i.e. TiiT_{i} \neq i for each ii.

After that the candidate hunters are left on Zevil Island for a week; there they can steal each other's badges. At the end of the week the fourth phase of the exam ends and it is recorded who has which badges. The score of a participant ii is the sum of the points that each of the badges he ended up with give him. The badges with numbers ii and TiT_{i} would give him KK points each, while all other badges would only be worth 11 point to him. The participants with at least 2K2K points pass the phase successfully, while all others fail.

Obviously, it is impossible for everyone to advance to the next phase. You wonder what the best possible outcome is, taking into account that you are more attached to some characters and less so to other ones. More specifically, for participant ii you feel LiL_{i} amount of attachment (in some units of measurement). You want to know the maximum possible value of the sum of all LmL_{m} where mm are the numbers of the participants who managed to get a score of at least 2K2K points.

The problem is that there are a lot of participants and therefore a lot of possible combinations, so you find it very difficult to find the best one by hand. Fortunately, you live in the 21st century and there is a modern computer in front of you. You decide it would be best to write a program which finds the maximum possible value of the sum above when given the described type of input data.

Input

From the first line of the standard input you should read two positive integers: NN and KK - the number of participants and the number of points which a participant's own badge and his target's badge would be worth to him. From each of the next NN lines you should read two non-negative integers: TiT_{i} and LiL_{i} - the number of participant ii's target as well as how attached you feel to the participant.

Output

On the only line of the standard output you should print one non-negative integer: the maximum possible total attachment you feel towards the participants who managed to get at least 2K2K points.

Constraints

  • 2N1042 \leq N \leq 10^{4}
  • 1KN/21 \leq K \leq N/2, 0Li2×1040 \leq L_{i} \leq 2 \times 10^{4}
  • 0Ti<N0 \leq T_{i} < N
  • TiiT_{i} \neq i
  • TiTjT_{i} \neq T_{j} if iji \neq j

Subtask 1 (10 points)

  • N10N \leq 10

Subtask 2 (15 points)

  • N700N \leq 700
  • TPj=P(j+1) mod N T_{P_{j}} = P_{\left( j + 1 \right)\text{\ mod\ N\ }} and LPN1=0L_{P_{N - 1}} = 0

Subtask 3 (15 points)

  • N104N \leq 10^4
  • TPj=P(j+1) mod N T_{P_{j}} = P_{\left( j + 1 \right)\text{\ mod\ N\ }} and LPN1=0L_{P_{N - 1}} = 0

Subtask 4 (10 points)

  • N700N \leq 700
  • TPj=P(j+1) mod N T_{P_{j}} = P_{\left( j + 1 \right)\text{\ mod\ N\ }}

Subtask 5 (10 points)

  • N104N \leq 10^4
  • TPj=P(j+1) mod N T_{P_{j}} = P_{\left( j + 1 \right)\text{\ mod\ N\ }}

Subtask 6 (20 points)

  • N700N \leq 700

Subtask 7 (20 points)

  • N104N \leq 10^4

Here PP is an arbitrary permutation of the numbers between 00 and N1N - 1 where P0=0P_{0} = 0.
Note: (j+1) mod N\left( j + 1 \right)\text{\ mod\ N} is the remainder of (j+1)\left( j + 1 \right) divided by NN.

Examples

stdin

8 2
5 12
6 111
4 101
0 13
1 105
7 14
2 108
3 9

stdout

324

Explanation

The successful participants are 1, 4 and 6. Here is one possible solution: participant 1 ends up with badges 1 and 6, participant 4 with badges 0, 4 and 7 and participant 6 with badges 2, 3 and 5. The sum is L1+L4+L6=111+105+108=324L_{1} + L_{4} + L_{6} = 111 + 105 + 108 = 324.

stdin

8 3
5 12
6 111
4 101
0 13
1 105
7 14
2 108
3 9

stdout

240

Log in or sign up to be able to send submissions!