题目描述

在漫画《Hunter × Hunter》的猎人考试第四阶段中，共有 N 名考生。每名考生都有一枚编号唯一的徽章，编号为 0..N-1。

同时，考官还准备了 N 张纸条，每张纸条上也写着一个 0..N-1 的编号。每位考生 i 抽取一张纸条，抽到的编号记为 T_i，表示他的目标考生编号。保证：

• T_i != i
• T_i 两两不同

也就是说，T 构成了一个没有自环的排列。

考试结束时，每位考生最终会持有若干枚徽章。对考生 i 而言：

• 编号为 i 的徽章值 K 分；
• 编号为 T_i 的徽章值 K 分；
• 其他任意徽章都只值 1 分。

如果考生 i 最终得到的总分 不少于 2K，则视为通过本阶段考试。

显然，不可能所有人都通过。现在你对每位考生 i 有一个“喜爱值” L_i。你希望安排最终徽章的归属方式，使得所有通过者的喜爱值总和最大。

请你求出这个最大值。

输入格式

第一行输入两个整数 N, K，分别表示考生人数和特殊徽章（本人徽章、目标徽章）的分值。

接下来 N 行，每行输入两个整数 T_i, L_i，表示考生 i 的目标编号以及你对他的喜爱值。

输出格式

输出一行一个非负整数，表示所有通过者喜爱值之和的最大可能值。

数据范围

• 2 <= N <= 10^4
• 1 <= K <= N / 2
• 0 <= L_i <= 2 × 10^4
• 0 <= T_i < N
• T_i != i
• T_i != T_j（当 i != j 时）

子任务与评分

其中 P 是一个满足 P_0 = 0 的 0..N-1 排列。

样例 #1

输入 #1

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

输出 #1

324

样例 #2

输入 #2

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

输出 #2

240

说明

对于样例 1，一种最优方案是让考生 1 最终持有徽章 1 和 6，考生 4 持有徽章 0、4、7，考生 6 持有徽章 2、3、5。这样通过的考生为 1, 4, 6，答案为：

L_1 + L_4 + L_6 = 111 + 105 + 108 = 324