비밀번호 찾기

브실이는 집에 들어가고 싶지만, 도어락의 비밀번호를 까먹어버렸다. 도어락의 비밀번호는 $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$라는 것을 의미한다.

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

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