비밀번호 찾기

브실이는 집에 들어가고 싶지만, 도어락의 비밀번호를 잊어버렸다. 도어락의 비밀번호는 $1$부터 $9$까지의 숫자가 각각 최대 $1$번씩 들어간 $N$자리의 정수이다. 브실이는 비밀번호를 한 번 입력할 때마다 $X$초가 걸린다. 도어락에 비밀번호를 연속으로 3번 입력해 모두 실패할 때마다, $Y$초 동안 비밀번호를 입력할 수 없게 된다. $Y$초를 기다리면 비밀번호 입력 횟수가 초기화된다.

집에 최대한 빨리 들어가고 싶었던 브실이는 곰곰이 생각한 끝에 비밀번호의 일부 정보를 떠올렸다. 브실이는 이 정보를 활용해, 현재 입력 실패 횟수가 0회인 도어락에 가능한 비밀번호를 모두 한 번씩 입력해 보기로 했다. 브실이가 집에 들어가는 데 걸리는 최대 시간을 구해보자.

첫 번째 줄에 비밀번호의 자릿수 $N$과 브실이가 비밀번호에 대해 기억하는 정보의 수 $M$이 공백으로 구분되어 주어진다. ($3 \le N \le 9$, $0 \le M \le N$)

두 번째 줄에 비밀번호를 입력하는 데 걸리는 시간 $X$와 비밀번호를 입력할 수 없는 시간 $Y$가 공백으로 구분되어 주어진다. ($1 \le X, Y \le 10$)

세 번째 줄부터 $M$개의 줄에 걸쳐 비밀번호에 대한 정보 $a$, $b$가 공백으로 구분되어 주어진다. ($0 \le a \le N$, $1 \le b \le 9$)

• $a \neq 0$이면, 비밀번호의 $a$번째 자리의 값이 $b$라는 뜻이다.
• $a = 0$이면, 비밀번호 중 한 자리의 값이 $b$라는 뜻이다.

같은 자리나 같은 숫자에 대한 정보는 여러 번 주어지지 않는다.

가진 정보를 활용해 브실이가 집에 들어가는 데 걸리는 최대 시간을 초 단위로 출력한다.