Knight's game X39759

Consider a chess board with n rows (indexed 0, 1, …, n−1 from top to bottom) and m columns (indexed 0, 1, …, m−1 from left to right). Each position of the board is determined by a pair (r, c), where r is the index of the row and c is the index of the column.

Let us define the following game. We begin with a knight (see the figure to recall how it moves) at the upper left corner. Given a sequence of goal positions of the board p₁, p₂, ..., p_k, we have to move the knight to goal position p₁ doing knight jumps; from there we have to get to goal position p₂, doing knight jumps; and so on until getting to the last goal position p_k. For each goal we reach, we get W points. But for each knight jump we do, we lose L points. The match is over when the next goal position cannot be reached, or we decide to stop moving. What is the maximum score that we can get if we play optimally?

Input

Input contains different cases, only with integer numbers. Each case starts with n and m, followed by W and L. Finally, we have k and the k goal positions represented by pairs of integers r_i c_i separated by blank spaces, where 0 ≤ r_i < n and 0 ≤ c_i < m. It holds that 2 ≤ n, m ≤ 5000, that n · m ≤ 10⁴, that 1 ≤ W, L ≤ 100 and that 1 ≤ k ≤ min(n · m, 1000).

Output

For each case, write in a line the maximum score that can be achieved if we play optimally.