47번 - 예쁜 초콜릿과 숫자놀이

코코는 화이트와 다크 초콜릿을 가지고 놀고 있다. 화이트 초콜릿 $N$개와 다크 초콜릿 $N$개를 배열했을 때, 다음의 조건을 만족하는 배열을 "예쁜 초콜릿"이라고 한다. $(X_1,X_2, \cdots, X_n)$은 초콜릿 배열 $X_1$, $X_2$, $\cdots$, $X_n$을 순서대로 이어 붙인 것을 뜻한다. \begin{itemize} \item (화이트, 다크)는 예쁜 초콜릿이다. \item (화이트, 예쁜 초콜릿, 다크)는 예쁜 초콜릿이다. \item (예쁜 초콜릿, 예쁜 초콜릿)은 예쁜 초콜릿이다. \item 위의 3가지 규칙으로 만들 수 없는 초콜릿 배열은 예쁜 초콜릿이 아니다. \end{itemize} 어떤 초콜릿 배열의 "점수"는 다음과 같이 계산한다. 특정한 정수 $a$에서 시작해서, 왼쪽부터 순서대로 화이트 초콜릿이 있으면 $b$를 더하고, 다크 초콜릿이 있으면 $c$를 곱한다. 마지막에 얻은 값을 $10^5$로 나눈 나머지가 이 초콜릿 배열의 점수이다. 코코는 예쁜 초콜릿 중에서 가장 점수가 높은 초콜릿 배열을 찾고 싶다. 코코를 위해 얻을 수 있는 가장 높은 점수를 계산해주자.

첫 줄에 정수 $N$, $a$, $b$, $c$가 순서대로 주어진다. ($1 \le N \le 15$, $1 \le a, b, c \lt 10^5$)

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