HUNTER×HUNTER#10896

HUNTER×HUNTER

1,7 секунди

256 мегабайтів

Дуже складна

У першій арці популярної манги "Hunter x Hunter" головний герой Ґон та його друзі беруть участь у іспиті на мисливця. На його четвертому етапі кожен з $N$ учасників отримує значок із унікальним номером від $0$ до $N - 1$ N - 1. Крім того, у чашу кладуть $N$ папірців, знову з унікальними номерами від $0$ до $N - 1$ N - 1. Кожен учасник $i$ витягує з чаші папірць (і залишає його собі); папірць, який він отримав містить число $T_{i}$ T_i, номер його цілі. Відомо, що ніхто не отримав папірць з власним номером, тобто $T_{i} \neq = i$ T_i \neq i для кожного $i$ .

Після цього кандидатів-мисливців залишають на острові Зевіль на тиждень; там вони можуть викрасти значки одне одного. В кінці тижня закінчується четвертий етап іспиту, і записується хто має які значки. Оцінка учасника $i$ — це сума балів, за кожен із значків з якими він залишився. Значки з номерами $i$ та $T_{i}$ T_i можуть принести учаснику $K$ балів кожен, тоді як усі інші значки можуть принести йому лише один бал. Учасники, що мають щонайменше $2 K$ балів, проходять етап успішно, тоді як усі інші зазнають невдачі.

Очевидно, що неможливо кожному перейти до наступного етапу. Вам цікаво, який є найкращий можливий результат, беручи до уваги, що ви більш прив'язані до одних учасників і менше до інших. Більш конкретно, до учасника $i$ ви прив'язані з $L_{i}$ L_i кількістю прив'язаності (у деяких одиницях виміру). Ви хочете дізнатися максимально можливе значення суми всіх $L_{m}$ L_m, де $m$ це кількість учасників, яким вдалося отримати щонайменше $2 K$ балів.

Проблема в тому, що учасників багато, а отже, багато можливих комбінацій, тому вам дуже важко знайти максимальне значення самостійно. На щастя, ви живете в 21 столітті, і перед вами сучасний комп'ютер. Ви вирішили, що найкраще буде написати програму, яка знаходить максимально можливе значення суми, що описана вище, за вхідними даними.

Вхідні дані

У першому рядку стандартного вводу міститься два натуральних числа: $N$ та $K$ — кількість учасників та кількість балів, які отримує учасник за власний значок та значок його цілі. Кожен з $N$ наступних рядків містить два цілих невід'ємних числа: $T_{i}$ T_i та $L_{i}$ L_i — номер цілі $i$ -го учасника, а також ваша прив'язаність до учасника.

Вихідні дані

В єдиному рядку стандартного виводу слід надрукувати одне ціле невід'ємне число: максимально можливу сумарну кількість прив'язаності, до учасників, яким вдалося отримати щонайменше $2 K$ балів.

Приклади

Приклад 1

Приклад 2

Примітка

Учасниками що пройшли четвертий етап є 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.

Оцінювання

Для того, щоб отримати бали за деяку підзадачу, ваше рішення повинне пройти всі тести підзадачі.

Підзадачі наступні:

Підзадача	Бали	$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.

2 \leq N \leq 1 0^{4}, 1 \leq K \leq N /2, 0 \leq L_{i} \leq 2 \times 1 0^{4}, 0 \leq T_{i} < N, T_{i} \neq = i, T_{i} \neq = T_{j} якщо i \neq = j

2 \leq N \leq 10^{4}, \quad 1 \leq K \leq N/2, \quad 0 \leq L_i \leq 2 \times 10^{4}, \quad 0 \leq T_i < N, \quad T_i \neq i, \quad T_i \neq T_j \text{ якщо } i \neq j