비밀번호 찾기

시간 제한1초메모리 제한1024 MB

요약

단서에 맞는 모든 N자리 비밀번호를 시도할 때, 시도당 X초와 연속 3회 실패마다 Y초 대기가 걸리는 상황에서 집에 들어가기까지 걸리는 최대 시간을 구한다.

난이도: 보통10점 중 6점
유형: 완전 탐색, 조합론, 구현, 수학
정답자: 아직 제출이 없습니다

문제

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

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

출력

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

예제2

예제 1
입력
```
4 4
3 10
1 2
0 1
0 3
4 8
```
예상 출력
```
6
```
예제 2
입력
```
4 0
3 10
```
예상 출력
```
19142
```