Una empresa tiene $n$ servidores, numerados del $1$ al $n$. El $i$-ésimo servidor ejecuta $a_i$ servicios.
A veces los servidores pueden apagarse, por lo que se ha definido un servidor de respaldo para cada servidor. Para un servidor con número $i$, el respaldo es el servidor con número $p_i$. Si para el $i$-ésimo servidor $p_i = i$, entonces es un servidor de alta fiabilidad y nunca se apaga.
Para cualesquiera dos servidores distintos $i$ y $j$, sus números de servidor de respaldo $p_i$ y $p_j$ son distintos. Por lo tanto, $p$ es una permutación de longitud $n$, lo que significa que cada número del $1$ al $n$ aparece exactamente una vez entre los valores $p_1, \dots, p_n$.
El proceso de apagado de servidores ocurre de la siguiente manera: si el servidor $i$ se apaga, todos los servicios que se ejecutan en él se trasladan al servidor con número $p_i$, y el servidor $i$ es reemplazado por un nuevo servidor en el que no se ejecuta ningún servicio. El número de este servidor y el número de su servidor de respaldo permanecen sin cambios. La transferencia de servicios y el reemplazo del servidor es un proceso muy rápido, durante el cual no pueden ocurrir nuevos apagados.
La empresa planea realizar una prueba de rendimiento del sistema. Para ello, se apagarán a lo sumo $k$ servidores. Los apagados se realizan secuencialmente, es decir, no hay dos servidores que se apaguen simultáneamente. Determine la cantidad máxima de servicios que pueden terminar en un solo servidor después de apagar a lo sumo $k$ servidores.
Entrada
La primera línea contiene dos enteros $n$ y $k$ ($1 \leqslant k < n \leqslant 10^5$) — la cantidad de servidores y la cantidad máxima de servidores que se pueden apagar.
La segunda línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($0 \leqslant a_i \leqslant 10^9$) — la cantidad de servicios que se ejecutan en los servidores.
La tercera línea contiene $n$ enteros $p_1, p_2, \dots, p_n$ ($1 \leqslant p_i \leqslant n$) — los números de los servidores de respaldo.
Salida
Imprima un único entero — la respuesta al problema.
Subtareas
| Subtarea | Puntos | Restricciones | Subtareas requeridas |
|---|---|---|---|
| 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 |
Ejemplos
Entrada 1
4 2 6 10 7 9 2 3 4 1
Salida 1
26
Entrada 2
3 1 1000000000 993 2010 1 3 2
Salida 2
1000000000
Entrada 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
Salida 3
23
Nota
Considere el orden de los apagados de servidores que permite alcanzar la respuesta máxima en el primer ejemplo.
Recuerde cómo se realizan las transferencias de servicios cuando los servidores se apagan:
| Servidor | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Respaldo | 2 | 3 | 4 | 1 |
El segundo servidor se apaga primero; sus servicios se trasladan al tercer servidor, por lo que ahora hay $10 + 7 = 17$ servicios en el tercer servidor.
El tercer servidor se apaga en segundo lugar; sus servicios se trasladan al cuarto servidor, después de lo cual hay $9 + 17 = 26$ servicios en el cuarto servidor.
Para una mejor comprensión, vea la tabla siguiente, que registra la cantidad de servicios en cada servidor durante el proceso descrito anteriormente.
| Etapa | $a_1$ | $a_2$ | $a_3$ | $a_4$ |
|---|---|---|---|---|
| Antes del primer apagado | 6 | 10 | 7 | 9 |
| Después de apagar el servidor 2 | 6 | 0 | 17 | 9 |
| Después de apagar el servidor 3 | 6 | 0 | 0 | 26 |
Si el tercer servidor se hubiera apagado primero y el segundo después, el proceso se vería así:
| Etapa | $a_1$ | $a_2$ | $a_3$ | $a_4$ |
|---|---|---|---|---|
| Antes del primer apagado | 6 | 10 | 7 | 9 |
| Después de apagar el servidor 3 | 6 | 10 | 0 | 16 |
| Después de apagar el servidor 2 | 6 | 0 | 10 | 16 |
En este caso, la cantidad máxima de servicios en un servidor sería 16, que no es la respuesta óptima.
En el segundo ejemplo, una de las opciones posibles es que ningún servidor se apague. Entonces hay $1000000000$ servicios en el primer servidor, que es la respuesta al problema. Si el servidor 2 o 3 se apaga, la cantidad máxima de servicios también estará en el primer servidor.