| Автор: | Антон Карабанов | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
В школе чародейства и волшебства Хогвартс четыре факультета (обозначим их числами от 1 до 4).
В результате последних приказов Министерства магии по оптимизации учебного процесса и равномерного распределения нагрузки среди преподавателей школы, алгоритм работы Распределяющей шляпы теперь описывается следующим набором правил:
1) Очередной абитуриент зачисляется на факультет, в котором меньше всего студентов. Если таких факультетов несколько, зачисление производится на факультет с наименьшим номером.
2) Запрещается двух абитуриентов подряд зачислять на один и тот же факультет. Если факультет, в который был зачислен предыдущий абитуриент по прежнему имеет в своём составе меньше всего студентов, зачисление производится на тот факультет из трёх оставшихся, в котором меньше всего студентов (при равенстве опять-таки выбирается факультет с меньшим номером).
По известному количеству студентов на факультетах, определите, какое минимальное количество новых абитуриентов нужно пропустить через Распределяющую шляпу, чтобы на всех факультетах училось равное число юных волшебников.
Четыре строки входных данных содержат четыре неотрицательных целых числа: a, b, c и d.
Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.
Выведите одно неотрицательное целое число — ответ на вопрос задачи.
1 ≤ a, b, c, d ≤ 1015
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при max(a, b, c, d) ≤ 1000, получат не менее 50 баллов.
В первом примере на всех факультетах равное число студентов. Новых абитуриентов принимать не нужно.
Во втором примере распределение будет происходить следующим образом:
Первый абитуриент распределяется на факультет №2 (там меньше всего студентов). Теперь на факультетах 3, 1, 1 и 2 студента.
Второй абитуриент распределяется на факультет №3 (есть 2 факультета с наименьшим числом студентов: №2 и №3, но №2 снова выбрать нельзя). Теперь на факультетах 3, 1, 2 и 2 студента.
Третий абитуриент распределяется на факультет №2. Теперь на факультетах 3, 2, 2 и 2 студента.
Четвёртый абитуриент распределяется на факультет №3 (есть 3 факультета с наименьшим числом студентов: №2, №3 и №4, но №2 снова выбрать нельзя, а у №3 номер меньше, чем у №4). Теперь на факультетах 3, 2, 3 и 2 студента.
Пятый абитуриент распределяется на факультет №2 (есть 2 факультета с наименьшим числом студентов: №2 и №4, но у №2 номер меньше, чем у №4). Теперь на факультетах 3, 3, 3 и 2 студента.
Шестой абитуриент распределяется на факультет №4. Теперь на факультетах равное число студентов.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|