Minimum energy × delay product

Paulo works for a large company called Ábaco Computadores e Manutenções (ACM). His job is to maintain the computers of ACM clients spread all over the country, so he spends a good number of hours per week inside airplanes. He always carries his laptop and gets work done during the flights.

Laptop batteries do not last long. While looking for ways to stretch the battery during a flight, Paulo learned that modern processors run at several frequency levels and trade performance for power. His first idea was to pin the laptop at the lowest frequency. That turned out to be useless: programs ran so slowly that there was no time to finish every task, and the remaining charge had nothing left to do.

How much a frequency level affects performance differs from program to program, depending on whether memory, the CPU, or I/O is the bottleneck. Since modern processors let software change the frequency level, Paulo plans to pick a level per program so the battery lasts longer while performance stays reasonable. To account for energy and performance together he uses a well known metric, the energy × delay product (EDP, Energy × Delay Product).

Paulo has the list of programs to run in order, the time and the energy each program needs at each frequency level, and the energy a frequency change costs. The problem is that, like most system administrators, he does not enjoy programming, so he asked you, a good friend and an expert in algorithms, for help.

The processor supports $F$ frequency levels numbered 1 to $F$, and it sits at level 1 when a test case starts. The programs run in order from 1 to $P$. Running program $p$ at level $f$ costs $E_{p,f}$ joules and $A_{p,f}$ milliseconds, so the EDP of that run is $E_{p,f} \times A_{p,f}$. Every frequency change costs $E$ joules and $A$ milliseconds, no matter which level it starts from and which level it ends at, so the EDP of a change is $E \times A$. The total EDP is the sum over the $P$ runs and every change. That is, if program $p$ runs at level $f_p$ and $C$ changes happen, then

$\text{EDP} = \sum_{p=1}^{P} E_{p,f_p} \times A_{p,f_p} + C \times E \times A$

Find the plan that minimizes the total EDP and report that value.

The input contains several test cases. The first line of a test case has four integers $F$, $P$, $E$, and $A$: the number of frequency levels the processor supports ($1 \le F \le 20$), the number of programs to run in order ($1 \le P \le 5000$), the energy in joules to change between any two frequency levels ($1 \le E \le 100$), and the time in milliseconds to change between any two frequency levels ($1 \le A \le 100$). Frequency levels are identified by the integers 1 to $F$, and programs by the integers 1 to $P$.

The next $P \times F$ lines describe the programs, $F$ lines per program. The first $F$ lines belong to program 1, the next $F$ lines to program 2, and so on. The $f$-th line among the $F$ lines of program $p$ has two integers $E_{p,f}$ and $A_{p,f}$, the energy in joules and the time in milliseconds needed to run program $p$ at frequency level $f$, with $1 \le E_{p,f} \le 1000$ and $1 \le A_{p,f} \le 1000$.

At the start of every test case the processor is at frequency level 1. The end of the input is a line with $F = P = E = A = 0$, which is not a test case.

For each test case, print one line with the minimum EDP for running programs 1 to $P$ in the order they appear in the input.