계산기

정보학 숙제로 학생들은 다음과 같이 동작하는 특별한 계산기를 만들라는 과제를 받았다.

먼저 사용자는 양의 정수 $n$을 입력하고, 이 수가 화면에 표시된다. 그다음 사용자는 세 개의 버튼 A, B, C를 누를 수 있다.

버튼 A를 누르면 화면에 표시된 수가 2로 나누어진다. 화면의 수가 홀수이면 나머지는 버린다. 예를 들어 이 연산의 결과는 80에 대해 40이고, 239에 대해 119이다.

버튼 B를 누르면 화면에 표시된 수에 1을 더한 뒤 그 결과를 2로 나눈다. 나눗셈의 나머지는 버린다. 예를 들어 이 연산의 결과는 80에 대해 40이고, 239에 대해 120이다.

버튼 C를 누르면 다음과 같은 일이 일어난다. 화면에 표시된 수가 양수이면 그 수에서 1을 뺀 뒤 결과를 2로 나누고, 나머지는 버린다. 버튼 C를 누르기 전에 화면에 0이 표시되어 있었다면 그 수는 그대로 남는다. 예를 들어 이 연산의 결과는 80에 대해 39이고, 239에 대해 119이다.

사용자는 수 $n$을 입력한 뒤 정해진 순서로 연산 버튼을 누르려고 한다. 구체적으로 그는 버튼 A를 총 $a$번, 버튼 B를 $b$번, 버튼 C를 $c$번 누를 계획이다. 그는 이러한 연산을 수행한 결과 얻을 수 있는 가장 작은 수가 무엇인지 궁금해졌다.

입력된 수 $n$과 계산기에서 누른 서로 다른 종류의 연산 횟수를 나타내는 수 $a$, $b$, $c$에 따라 계산기 조작 결과 얻을 수 있는 가장 작은 수를 구하는 프로그램을 작성해야 한다.

입력 파일에는 네 개의 정수 $n$, $a$, $b$, $c$가 들어 있다 ($1 \le n \le 10^{18}$, $0 \le a, b, c \le 60$). 수는 한 줄에 주어지며, 인접한 수는 공백 하나로 구분된다.

계산기 조작 결과 사용자가 얻을 수 있는 가장 작은 수 하나를 출력해야 한다.

예제에서 사용자는 다음과 같이 최적으로 행동해야 한다. 버튼 B를 눌러 36을 얻고, 버튼 A를 눌러 18을 얻고, 버튼 C를 눌러 8을 얻고, 두 번째로 버튼 A를 눌러 4를 얻는다.