Задача 2. Калькулятор

Автор:Центральная предметно-методическая комиссия   Ограничение времени:1 сек
Входной файл:calc.in   Ограничение памяти:256 Мб
Выходной файл:calc.out  
Максимальный балл:100  

Условие

В качестве домашнего задания по информатике ученикам предложено разработать специальный калькулятор, который устроен следующим образом.

Сначала пользователь вводит целое положительное число 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 ≤ n ≤ 1018, 0 ≤ a, b, c ≤ 60

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
nДополнительные ограничения на a, b, c
1261 ≤ n ≤ 1090 ≤ (a + b + c) ≤ 7
2231 ≤ n ≤ 1018c = 0
3241 ≤ n ≤ 1018b = 0
4271 ≤ n ≤ 10181, 2, 3

Описание подзадач и системы оценивания

По запросу сообщается результат окончательной проверки на каждом тесте.

Пояснения к примеру

В примере пользователю необходимо оптимально действовать следующим образом: нажать на кнопку B и получить число 36, затем нажать на кнопку A и получить число 18, затем нажать на кнопку C и получить число 8, затем второй раз нажать на кнопку A и получить число 4.

Примеры тестов

Входной файл (calc.in) Выходной файл (calc.out)
1
72 2 1 1
4

0.043s 0.007s 15