HUNTER×HUNTER

Входни данни

На първия ред на стандартния вход се въвеждат две цели положителни числа: $N$ и $K$ — броят участници и броят точки, които баджът на даден играч, както и баджът на мишената му, биха му донесли. На всеки от следващите $N$ реда се въвеждат по две цели неотрицателни числа: $T_{i}$ T_i и $L_{i}$ L_i — номерът на мишената на участник $i$ , както и колко привързаност изпитвате към участника.

Изходни данни

На единствения ред на стандартния изход изведете едно цяло неотрицателно число: максималната възможна обща привързаност, която изпитвате към участниците, които са събрали поне $2 K$ точки.

Примери

Пример 1

Loading

Пример 2

Loading

Бележка

Обяснение на примерен тест 1

В тест 1 успешните участници са 1, 4 и 6. Например, участник 1 завършва с баджове 1 и 6, участник 4 — с баджове 0, 4 и 7, а участник 6 — с баджове 2, 3 и 5. Сумата е $L_{1} + L_{4} + L_{6} = 111 + 105 + 108 = 324$ L_1 + L_4 + L_6 = 111 + 105 + 108 = 324.

Точкуване

За да получите точките за дадена подзадача, трябва програмата Ви да премине всички тестове в нея.

Ограничения:

2 \leq N \leq 1 0^{4}

2 \leq N \leq 10^4

1 \leq K \leq N /2

1 \leq K \leq N/2

0 \leq L_{i} \leq 2 \times 1 0^{4}

0 \leq L_i \leq 2 \times 10^4

0 \leq T_{i} < N

0 \leq T_i < N

T_{i} \neq = i

T_i \neq i

T_{i} \neq = T_{j} ако i \neq = j

T_i \neq T_j \text{ ако } i \neq j

Подзадачите са както следва:

Подзадача	Точки	$N \leq$	Допълнителни ограничения
1	10	10	Няма
2	15	700	$T_{P_{j}} = P_{(j + 1) mod N}$ T_{P_j} = P_{(j+1) \bmod N} и $L_{P_{N - 1}} = 0$ L_{P_{N-1}} = 0
3	15	$1 0^{4}$ 10^4	$T_{P_{j}} = P_{(j + 1) mod N}$ T_{P_j} = P_{(j+1) \bmod N} и $L_{P_{N - 1}} = 0$ L_{P_{N-1}} = 0
4	10	700	$T_{P_{j}} = P_{(j + 1) mod N}$ T_{P_j} = P_{(j+1) \bmod N}
5	10	$1 0^{4}$ 10^4	$T_{P_{j}} = P_{(j + 1) mod N}$ T_{P_j} = P_{(j+1) \bmod N}
6	20	700	Няма
7	20	$1 0^{4}$ 10^4	Няма

Тук $P$ е произволна пермутация на числата от $0$ до $N - 1$ N - 1, където $P_{0} = 0$ P_0 = 0.