Finding the password

Busil wants to get into the house, but he has forgotten the password for the digital door lock. The password is an $N$-digit integer in which each digit from $1$ to $9$ appears at most $1$ time. Each time Busil enters a password, it takes $X$ seconds. Whenever he enters three passwords in a row and all three fail, he cannot enter a password for $Y$ seconds. After waiting $Y$ seconds, the count of failed attempts resets.

Busil wants to get inside as quickly as possible. After some thought, he remembered part of the password. Using this information, he decided to try every possible password once on the door lock, which currently has zero failed attempts. Find the maximum time it takes Busil to get into the house.

The first line contains the password length $N$ and the number $M$ of pieces of information Busil remembers, separated by a space. ($3 \le N \le 9$, $0 \le M \le N$)

The second line contains the integer $X$, the time to enter a password, and the integer $Y$, the time during which passwords cannot be entered, separated by a space. ($1 \le X, Y \le 10$)

From the third line onward, the next $M$ lines each contain integers $a$ and $b$, separated by a space. ($0 \le a \le N$, $1 \le b \le 9$)

• If $a \neq 0$, the digit at position $a$ of the password is $b$.
• If $a = 0$, one of the digits of the password is $b$.

No position or digit appears in more than one piece of information.

Print the maximum time, in seconds, that it takes Busil to get into the house using the information he remembers.