У компании есть $n$ серверов, пронумерованных от $1$ до $n$. На $i$-м сервере работает $a_i$ служб.
Иногда серверы могут отключаться, поэтому для каждого сервера определён резервный сервер. Для сервера с номером $i$ резервным является сервер с номером $p_i$. Если для $i$-го сервера $p_i = i$, то это сервер повышенной надёжности, и он никогда не отключается.
Для любых двух различных серверов $i$ и $j$ номера их резервных серверов $p_i$ и $p_j$ различны. Таким образом, $p$ является перестановкой длины $n$, то есть каждое число от $1$ до $n$ встречается среди значений $p_1, \dots, p_n$ ровно один раз.
Процесс отключения серверов происходит следующим образом: если сервер $i$ отключается, все службы, работающие на нём, перемещаются на сервер с номером $p_i$, а сервер $i$ заменяется новым сервером, на котором не работает ни одной службы. Номер этого сервера и номер его резервного сервера остаются неизменными. Перенос служб и замена сервера — очень быстрый процесс, во время которого не может произойти новых отключений.
Компания планирует провести тест производительности системы. Для этого будет отключено не более $k$ серверов. Отключения выполняются последовательно, то есть никакие два сервера не отключаются одновременно. Определите максимальное количество служб, которое может оказаться на одном сервере после отключения не более $k$ серверов.
Входные данные
Первая строка содержит два целых числа $n$ и $k$ ($1 \leqslant k < n \leqslant 10^5$) — количество серверов и максимальное количество серверов, которое может быть отключено.
Вторая строка содержит $n$ целых чисел $a_1, a_2, \dots, a_n$ ($0 \leqslant a_i \leqslant 10^9$) — количество служб, работающих на серверах.
Третья строка содержит $n$ целых чисел $p_1, p_2, \dots, p_n$ ($1 \leqslant p_i \leqslant n$) — номера резервных серверов.
Выходные данные
Выведите одно целое число — ответ на задачу.
Подзадачи
| Подзадача | Баллы | Ограничения | Необходимые подзадачи |
|---|---|---|---|
| 1 | 15 | $n \leqslant 1000, k = 1$ | — |
| 2 | 27 | $n \leqslant 1000$ | 1 |
| 3 | 21 | $p_i = i \pmod n + 1$ | — |
| 4 | 37 | — | 1, 2, 3 |
Примеры
Входные данные 1
4 2 6 10 7 9 2 3 4 1
Выходные данные 1
26
Входные данные 2
3 1 1000000000 993 2010 1 3 2
Выходные данные 2
1000000000
Входные данные 3
11 5 3 5 12 7 5 9 2 6 0 9 4 2 8 9 6 5 11 3 1 10 7 4
Выходные данные 3
23
Примечание
Рассмотрим порядок отключения серверов, позволяющий получить максимальный ответ в первом примере.
Напомним, как происходит перенос служб при отключении серверов:
| Сервер | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Резервный | 2 | 3 | 4 | 1 |
Сначала отключается второй сервер; его службы перемещаются на третий сервер, поэтому теперь на третьем сервере $10 + 7 = 17$ служб.
Вторым отключается третий сервер; его службы перемещаются на четвёртый сервер, после чего на четвёртом сервере становится $9 + 17 = 26$ служб.
Для лучшего понимания см. таблицу ниже, в которой указано количество служб на каждом сервере во время описанного процесса.
| Этап | $a_1$ | $a_2$ | $a_3$ | $a_4$ |
|---|---|---|---|---|
| До первого отключения | 6 | 10 | 7 | 9 |
| После отключения сервера 2 | 6 | 0 | 17 | 9 |
| После отключения сервера 3 | 6 | 0 | 0 | 26 |
Если бы сначала отключился третий сервер, а затем второй, процесс выглядел бы так:
| Этап | $a_1$ | $a_2$ | $a_3$ | $a_4$ |
|---|---|---|---|---|
| До первого отключения | 6 | 10 | 7 | 9 |
| После отключения сервера 3 | 6 | 10 | 0 | 16 |
| После отключения сервера 2 | 6 | 0 | 10 | 16 |
В этом случае максимальное количество служб на сервере было бы 16, что не является оптимальным ответом.
Во втором примере один из возможных вариантов — не отключать ни одного сервера. Тогда на первом сервере будет $1000000000$ служб, что и является ответом на задачу. Если отключить сервер 2 или 3, максимальное количество служб также останется на первом сервере.