Joc de cavall X39759

Considerem un tauler d’escacs amb $n$ files (indexades $0$, $1$, $\ldots$, $n-1$ de dalt a baix) i $m$ columnes (indexades $0$, $1$, $\ldots$, $m-1$ d’esquerra a dreta). Cada posició del tauler queda determinada per un parell $(r, c)$, on $r$ és l’índex de la fila i $c$ l’índex de la columna.

Definim el següent joc. Es comença amb un cavall (vegeu la figura per recordar com es mou) a la cantonada superior esquerra. Donada una seqüència de posicions objectiu del tauler $p_{1}$, $p_{2}$, ..., $p_{k}$, es tracta de moure el cavall fins a la posició objectiu $p_{1}$ fent salts de cavall; d’allà hem d’arribar a la posició objectiu $p_{2}$, fent salts de cavall; i així successivament fins arribar a la darrera posició objectiu $p_{k}$. Per cada objectiu que assolim, aconseguim $W$ punts. Però per cada salt de cavall que fem, perdem $L$ punts. La partida acaba quan no es pot arribar a la posició objectiu següent, o quan decidim no fer més moviments. Quin és el nombre màxim de punts que es poden aconseguir si juguem de forma òptima?

Entrada

L’entrada conté diferents casos, només amb nombres enters. Cada cas comença amb $n$ i $m$, seguits de $W$ i $L$. Finalment, tenim $k$ i les $k$ posicions objectiu representades per parells d’enters $r_{i}$ $c_{i}$ separats per espais en blanc, on $0 \leq r_{i} < n$ i $0 \leq c_{i} < m$. Es compleix que $2 \leq n, m \leq 5000$, que $n \cdot m \leq 10^{4}$, que $1 \leq W, L \leq 100$ i que $1 \leq k \leq \min(n \cdot m, 1000)$.

Sortida

Per a cada cas, cal escriure en una línia el nombre màxim de punts que es poden aconseguir si juguem de forma òptima.