Chill...은 내가 가장 좋아하는 소수

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

요약

2×n 격자를 도미노로 빈틈없이 채우는데, 덮은 두 수의 합이 소수이면 a점, 아니면 b점을 얻을 때 최고 점수를 구한다. 좋은 타일과 나쁜 타일이 번갈아 나오는 패턴을 이용한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 정수론, 배열
정답자: 아직 제출이 없습니다

문제

$2 \times n$ 격자의 각 칸에 양의 정수가 하나씩 적혀 있다. 산지니는 이 격자 위에 $2 \times 1$ 타일 또는 $1 \times 2$ 타일로 격자를 빈틈없이 채워 점수를 얻는 게임을 하고자 한다. 이때 한 타일이 덮고 있는 수의 합이 소수라면 $a$ 점, 소수가 아니라면 $b$ 점을 얻게 된다. 산지니가 얻을 수 있는 최고 점수를 알려주자.

입력

첫 번째 줄에 격자의 크기 $n$ , 산지니가 얻게 될 점수 $a$ , $b$ 가 공백으로 구분되어 주어진다. ( $1 \le n \le 200\\,000;1 \le a, b \le 10$ )

두 번째 줄에 격자 $1$ 행에 적혀있는 수 $n$ 개가 순서대로 공백으로 구분되어 주어진다.

세 번째 줄에 격자 $2$ 행에 적혀 있는 수 $n$ 개가 순서대로 공백으로 구분되어 주어진다.

격자에 적혀있는 수는 $1$ 이상 $100\\,000$ 이하이다. 주어지는 모든 수는 정수이다.

출력

산지니가 얻을 수 있는 최고 점수를 출력한다.

예제2

예제 1
입력
```
2 2 3
2 2
3 3
```
예상 출력
```
6
```
예제 2
입력
```
2 3 2
2 2
3 3
```
예상 출력
```
6
```