Le célèbre artiste Karuna joue à un jeu de rythme.
L'artiste essaie de frapper les notes d'une chanson. La chanson est une séquence de $N$ notes.
Le système de score utilisé dans ce jeu est le suivant :
- Au début de la chanson (avant la première note), le score est de 0 et le bonus de combo est de 0.
- Chaque note a sa propre valeur. La valeur de la $i$-ème note est $A_i$.
- La valeur du bonus de combo est égale à 0 si Karuna manque la note actuelle, ou à $C_j$ si Karuna frappe cette note et qu'il y a $j$ notes consécutives que Karuna a frappées.
- Si Karuna frappe la $i$-ème note et que la longueur du combo après cela est $j$, la valeur $A_i \cdot C_j$ est ajoutée au score.
- Si Karuna manque la note, la longueur du combo est réinitialisée à 0. Si elle était non nulle auparavant (en d'autres termes, si Karuna a frappé la note précédente), alors le score de fin de combo $P$ est ajouté au score.
- Si Karuna frappe la dernière note de la chanson, le score de fin de combo $P$ est également ajouté au score.
Les compétences de Karuna lui permettent de ne pas frapper plus de $K$ notes pendant la chanson. Pour chaque note, il peut choisir de la frapper ou de la manquer, tant qu'il ne frappe pas plus de $K$ notes au total.
Étant donné tous les paramètres, déterminez le score maximum que Karuna peut obtenir.
Entrée
La première ligne de l'entrée contient trois entiers $N$, $K$ et $P$ ($1 \le N, K \le 2000$, $-10^9 \le P \le 10^9$) : respectivement le nombre de notes dans la chanson, le nombre maximum de notes que Karuna peut frapper, et le score de fin de combo.
La deuxième ligne contient $N$ entiers séparés par des espaces. Le $i$-ème nombre représente le score $A_i$ obtenu en frappant la $i$-ème note ($0 \le A_i \le 10^5$).
La troisième ligne contient $N$ entiers séparés par des espaces. Le $j$-ème nombre représente le score $C_j$ pour un combo de longueur $j$ ($-10^5 \le C_j \le 10^5$, et pour tout $1 \le j \le N - 1$, il est garanti que $C_j \ge C_{j+1}$).
Sortie
Affichez un seul entier : le score maximum que Karuna peut obtenir dans le jeu de rythme.
Exemples
Entrée 1
5 5 1 5 4 3 2 1 5 4 3 2 1
Sortie 1
57