시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.7 초 1024 MB119766.977%

문제

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 N participants gets a badge with a unique number between 0 and N − 1. Also, N pieces of paper again each with a unique number between 0 and N − 1 are put in a bowl. Each participant i draws a piece of paper from the bowl (and doesn’t return it); the piece of paper he gets shows the number Ti of his target. It is known that nobody drew their own number, i.e. Ti ≠ i for each i.

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 i is the sum of the points that each of the badges he ended up with give him. The badges with numbers i and Ti would give him K points each, while all other badges would only be worth 1 point to him. The participants with at least 2K 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 i you feel Li amount of attachment (in some units of measurement). You want to know the maximum possible value of the sum of all Lm where m are the numbers of the participants who managed to get a score of at least 2K 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 hunterxhunter which finds the maximum possible value of the sum above when given the described type of input data.

입력

From the first line of the standard input you should read two positive integers: N and K – 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 N lines you should read two non-negative integers: Ti and Li – the number of participant i’s target as well as how attached you feel to the participant.

출력

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 2K points.

제한

  • 2 ≤ N ≤ 104
  • 1 ≤ K ≤ N/2 0 ≤ Li ≤ 2 × 104
  • 0 ≤ Ti < N
  • Ti ≠ i
  • Ti ≠ Tj if i ≠ j

서브태스크

번호배점제한
110

N ≤ 10

215

N ≤ 700, TPj = P(j+1) mod N and LPN−1 = 0

315

N ≤ 104, TPj = P(j+1) mod N and LPN−1 = 0

410

N ≤ 700, TPj = P(j+1) mod N

510

N ≤ 104, TPj = P(j+1) mod N

620

N ≤ 700

720

N ≤ 104

Here P is an arbitrary permutation of the numbers between 0 and N − 1 where P0 = 0.

예제 입력 1

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

예제 출력 1

324

예제 입력 2

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

예제 출력 2

240

힌트

Explanation of sample test 1 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 = 324.

채점 및 기타 정보

  • 예제는 채점하지 않는다.