예쁜 초콜릿과 숫자놀이

면접 대비

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

요약

화이트 N개와 다크 N개로 만든 균형 잡힌 괄호 모양 배열 중 화이트는 b를 더하고 다크는 c를 곱해 10^5로 나눈 나머지가 최대인 점수를 구한다.

난이도: 보통10점 중 5점
유형: 백트래킹, 재귀, 수학, 완전 탐색
정답자: 아직 제출이 없습니다

문제

코코는 화이트와 다크 초콜릿을 가지고 놀고 있다. 화이트 초콜릿 $N$ 개와 다크 초콜릿 $N$ 개를 배열했을 때, 다음의 조건을 만족하는 배열을 "예쁜 초콜릿"이라고 한다. $(X\_1,X\_2, \cdots, X\_n)$ 은 초콜릿 배열 $X\_1$ , $X\_2$ , $\cdots$ , $X\_n$ 을 순서대로 이어 붙인 것을 뜻한다.

(화이트, 다크)는 예쁜 초콜릿이다.
(화이트, 예쁜 초콜릿, 다크)는 예쁜 초콜릿이다.
(예쁜 초콜릿, 예쁜 초콜릿)은 예쁜 초콜릿이다.
위의 3가지 규칙으로 만들 수 없는 초콜릿 배열은 예쁜 초콜릿이 아니다.

어떤 초콜릿 배열의 "점수"는 다음과 같이 계산한다. 특정한 정수 $a$ 에서 시작해서, 왼쪽부터 순서대로 화이트 초콜릿이 있으면 $b$ 를 더하고, 다크 초콜릿이 있으면 $c$ 를 곱한다. 마지막에 얻은 값을 $10^5$ 로 나눈 나머지가 이 초콜릿 배열의 점수이다.

코코는 예쁜 초콜릿 중에서 가장 점수가 높은 초콜릿 배열을 찾고 싶다. 코코를 위해 코코가 얻을 수 있는 가장 높은 점수를 계산해주자.

입력

첫 줄에 정수 $N$ , $a$ , $b$ , $c$ 가 순서대로 주어진다.

출력

화이트 초콜릿 $N$ 개와 다크 초콜릿 $N$ 개를 사용해 만들 수 있는 예쁜 초콜릿들의 점수의 최댓값을 한 줄에 출력한다.

제한

$1 \le N \le 15$
$1 \le a, b, c \lt 10^5$

예제3

예제 1
입력
```
1 3 5 7
```
예상 출력
```
56
```
예제 2
입력
```
2 3 5 7
```
예상 출력
```
637
```
예제 3
입력
```
2 10 10 100
```
예상 출력
```
1000
```