Comiendo setas P14827

Alicia y Benito tienen $n$ setas en común, y se las quieren comer todas en orden: primero la seta 1, luego la 2, … Cada seta será comida enteramente por Alicia o por Benito. Se sabe que comer la seta $i$-ésima provocaría satisfacción $A_i$ a Alicia, y satisfacción $B_i$ a Benito. Son buenos amigos, por lo que han decidido maximizar la suma de las satisfacciones de ambos, sin importar cuántas setas comerá cada uno.

Sin embargo, existe un problema. Como las setas tienen un gusto fuerte, si cualquiera de ellos se come la seta $j$ cuando la última seta que se había comido era la $i$, se deberá restar un cierto valor $T[i][j]$ a la satisfacción total obtenida.

¿Podéis calcular la máxima satisfacción total posible, si se decide quién se come cada seta de forma óptima?

Entrada

La entrada consiste en diversos casos, y sólo contiene números enteros no negativos. Cada caso empieza con cinco números $n$, $c$, $d$, $e$ y $p$. Siguen $A_1, ..., A_n$ y $B_1, ..., B_n$. Asumid $n \ge 1$, que $c$, $d$ y $e$ son menores que $p$, $p \le 1000$, y que todas las $A_i$ y las $B_i$ están entre 0 y 1000.

Los valores $c$, $d$, $e$ y $p$ se dan para definir la matriz $T[1..n][1..n]$ de forma implícita, de la forma siguiente: $$\begin{equation*} T[i][j] = \left\{ \begin{tabular}{lr} $c$, & si $i = 1$ y $j = 1$; \\ $(d \cdot T[i][j-1] + e) \bmod p$, & si $j > 1$; \\ $(d \cdot T[i-1][n] + e) \bmod p$, & \quad si $i > 1$ y $j = 1$. \end{tabular}\right. \end{equation*}$$ Esta definición de la matriz $T$ no tiene ningún truco, simplemente sirve para que la entrada sea relativamente pequeña y rápida de leer.

Salida

Para cada caso, escribid la máxima satisfacción posible.

Puntuación

• test-1:   Casos con $n \le 1000$ y donde $T$ sólo tiene ceros, como el Ejemplo 1.

• test-2:   Casos con $n \le 10$, como el Ejemplo 2.

• test-3:   Casos con $n \le 100$.

• test-4:   Casos con $n \le 1000$.