Une entreprise dispose de $n$ serveurs, numérotés de $1$ à $n$. Le $i$-ème serveur exécute $a_i$ services.
Il arrive que des serveurs s’arrêtent, aussi un serveur de secours a été défini pour chaque serveur. Pour un serveur de numéro $i$, le serveur de secours est celui de numéro $p_i$. Si pour le $i$-ème serveur on a $p_i = i$, alors il s’agit d’un serveur à haute fiabilité et il ne s’arrête jamais.
Pour deux serveurs distincts quelconques $i$ et $j$, les numéros de leurs serveurs de secours $p_i$ et $p_j$ sont distincts. Ainsi $p$ est une permutation de longueur $n$, ce qui signifie que chaque entier de $1$ à $n$ apparaît exactement une fois parmi les valeurs $p_1, \dots, p_n$.
Le processus d’arrêt des serveurs se déroule comme suit : si le serveur $i$ s’arrête, tous les services qui y tournent sont déplacés vers le serveur de numéro $p_i$, et le serveur $i$ est remplacé par un nouveau serveur sur lequel aucun service ne tourne. Le numéro de ce serveur et le numéro de son serveur de secours restent inchangés. Le transfert des services et le remplacement du serveur sont des opérations très rapides, pendant lesquelles aucun nouvel arrêt ne peut avoir lieu.
L’entreprise prévoit d’effectuer un test de performance du système. Pour cela, au plus $k$ serveurs seront arrêtés. Les arrêts sont effectués séquentiellement, c’est-à-dire que deux serveurs ne sont jamais arrêtés simultanément. Déterminez le nombre maximal de services qui peuvent se retrouver sur un seul serveur après avoir arrêté au plus $k$ serveurs.
Entrée
La première ligne contient deux entiers $n$ et $k$ ($1 \leqslant k < n \leqslant 10^5$) — le nombre de serveurs et le nombre maximal de serveurs pouvant être arrêtés.
La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($0 \leqslant a_i \leqslant 10^9$) — le nombre de services tournant sur les serveurs.
La troisième ligne contient $n$ entiers $p_1, p_2, \dots, p_n$ ($1 \leqslant p_i \leqslant n$) — les numéros des serveurs de secours.
Sortie
Affichez un unique entier — la réponse au problème.
Sous‑tâches
| Sous‑tâche | Points | Contraintes | Sous‑tâches requises |
|---|---|---|---|
| 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 |
Exemples
Entrée 1
4 2 6 10 7 9 2 3 4 1
Sortie 1
26
Entrée 2
3 1 1000000000 993 2010 1 3 2
Sortie 2
1000000000
Entrée 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
Sortie 3
23
Remarque
Considérons l’ordre des arrêts de serveurs qui permet d’obtenir la réponse maximale dans le premier exemple.
Rappelons comment les transferts de services s’effectuent quand des serveurs s’arrêtent :
| Serveur | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Secours | 2 | 3 | 4 | 1 |
Le deuxième serveur s’arrête en premier ; ses services sont déplacés vers le troisième serveur, qui se retrouve donc avec $10 + 7 = 17$ services.
Le troisième serveur s’arrête en second ; ses services sont déplacés vers le quatrième serveur, après quoi il y a $9 + 17 = 26$ services sur le quatrième serveur.
Pour mieux comprendre, voir le tableau ci‑dessous, qui enregistre le nombre de services sur chaque serveur pendant le processus décrit ci‑dessus.
| Étape | $a_1$ | $a_2$ | $a_3$ | $a_4$ |
|---|---|---|---|---|
| Avant le premier arrêt | 6 | 10 | 7 | 9 |
| Après l’arrêt du serveur 2 | 6 | 0 | 17 | 9 |
| Après l’arrêt du serveur 3 | 6 | 0 | 0 | 26 |
Si le troisième serveur s’était arrêté en premier, et le deuxième en second, le processus aurait ressemblé à ceci :
| Étape | $a_1$ | $a_2$ | $a_3$ | $a_4$ |
|---|---|---|---|---|
| Avant le premier arrêt | 6 | 10 | 7 | 9 |
| Après l’arrêt du serveur 3 | 6 | 10 | 0 | 16 |
| Après l’arrêt du serveur 2 | 6 | 0 | 10 | 16 |
Dans ce cas, le nombre maximal de services sur un serveur serait 16, ce qui n’est pas la réponse optimale.
Dans le deuxième exemple, l’une des options possibles est de n’arrêter aucun serveur. Il y a alors $1000000000$ services sur le premier serveur, ce qui constitue la réponse au problème. Si le serveur 2 ou 3 s’arrête, le nombre maximal de services se trouvera également sur le premier serveur.