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

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

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

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

Input

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

Output

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

Examples

Input 1

1 3 5 7

Output 1

56

Input 2

2 3 5 7

Output 2

637

Input 3

2 10 10 100

Output 3

1000

Note

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