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

문제

코코는 화이트와 다크 초콜릿을 가지고 놀고 있다. 화이트 초콜릿 $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$

힌트