Joc de cavall X39759

Considerem un tauler d’escacs amb n files (indexades 0, 1, …, n−1 de dalt a baix) i m columnes (indexades 0, 1, …, 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₁, p₂, ..., p_k, es tracta de moure el cavall fins a la posició objectiu p₁ fent salts de cavall; d’allà hem d’arribar a la posició objectiu p₂, 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 ≤ r_i < n i 0 ≤ c_i < m. Es compleix que 2 ≤ n, m ≤ 5000, que n · m ≤ 10⁴, que 1 ≤ W, L ≤ 100 i que 1 ≤ k ≤ min(n · 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.