El famoso artista Karuna está jugando a un juego de ritmo.
El artista está intentando acertar las notas de una canción. La canción es una secuencia de $N$ notas.
El sistema de puntuación utilizado en este juego es el siguiente:
- Al principio de la canción (antes de la primera nota), la puntuación es $0$ y el bono de combo es $0$.
- Cada nota tiene su propio valor. El valor de la $i$-ésima nota es $A_i$.
- El valor del bono de combo es igual a $0$ si Karuna falla la nota actual, o $C_j$ si Karuna acierta esta nota y hay $j$ notas seguidas que Karuna ha acertado.
- Si Karuna acierta la $i$-ésima nota y la longitud del combo después de eso es $j$, el valor de $A_i \cdot C_j$ se suma a la puntuación.
- Si Karuna falla la nota, la longitud del combo se restablece a $0$. Si era distinta de cero antes (en otras palabras, si Karuna acertó la nota anterior), entonces la puntuación de finalización de combo $P$ se suma a la puntuación.
- Si Karuna acierta la última nota de la canción, la puntuación de finalización de combo $P$ también se suma a la puntuación.
Las habilidades de Karuna le permiten acertar no más de $K$ notas durante la canción. Para cada nota, puede elegir acertarla o fallarla, siempre y cuando no acierte más de $K$ notas en total.
Dados todos los parámetros, determina la puntuación máxima que Karuna puede obtener.
Entrada
La primera línea de la entrada contiene tres enteros $N$, $K$ y $P$ ($1 \le N, K \le 2000$, $-10^9 \le P \le 10^9$): el número de notas en la canción, el número máximo de notas que Karuna puede acertar y la puntuación por ruptura de combo, respectivamente.
La segunda línea contiene $N$ enteros separados por espacios. El $i$-ésimo número representa el puntaje $A_i$ por acertar la $i$-ésima nota ($0 \le A_i \le 10^5$).
La tercera línea contiene $N$ enteros separados por espacios. El $j$-ésimo número representa el puntaje $C_j$ para un combo de longitud $j$ ($-10^5 \le C_j \le 10^5$, y para todo $1 \le j \le N - 1$, se garantiza que $C_j \ge C_{j+1}$).
Salida
Imprime un solo entero: la puntuación máxima que Karuna puede obtener en el juego de ritmo.
Ejemplos
Entrada 1
5 5 1 5 4 3 2 1 5 4 3 2 1
Salida 1
57