Тимофей очень любит играть в домино со своими друзьями. Друзей у Тимофея много, все хотят играть одновременно, поэтому стандартного комплекта им часто не хватает.
Стандартный набор традиционного домино включает в себя 28 костяшек. Костяшка домино представляет собой прямоугольную плитку, длина которой вдвое больше ширины. Её лицевая сторона разделена линией на две квадратные части. Каждая часть содержит от нуля до шести точек. В полном наборе представлены все комбинации пар от 0 до наибольшего количества точек на каждой из половинок костяшки. Тимофей выяснил, что в специализированных наборах домино возможное количество точек может доходить до девяти, двенадцати, пятнадцати, восемнадцати или быть произвольным.
Родители заказали для Тимофея особый набор домино и держат в секрете, какое наибольшее количество точек может быть расположено на половине костяшки. Однако Тимофей выяснил общее количество костяшек в наборе. Помогите Тимофею раскрыть секрет и узнать наибольшее количество точек.
Формат входных данных
В единственной строке входного файла записано натуральное число n - количество костяшек в полном наборе.
Формат выходных данных
В единственной строке выходного файла запишите одно целое неотрицательное число - наибольшее количество точек, которое может быть расположено на костяшках такого набора. Гарантируется, что такой ответ существует.
Ограничения
1 ≤ n ≤ 1018.
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Подзадача 1: 1 ≤ n ≤ 105, баллы: 50.
Подзадача 2: нет ограничений, баллы: 50.
Пояснения к примерам
В первом примере единственный полный набор из единственной костяшки состоит из дубля "пусто-пусто".
Во втором примере в полном нестандартном наборе, если наибольшее число точек на одной части костяшки равно трем, будет 10 костяшек.
В третьем примере в стандартном наборе домино, наибольшее число точек на одной части костяшки равно шести. Полный набор составляет 28 костяшек.
Сегодня - страшный день для всех одноклассников Тимофея, не готовых к зачету по теме "Системы счисления". Строгий учитель дал задание каждому ученику и не отпускает его из класса, пока не получит правильный ответ.
Задание представляет собой последовательность из n описаний. Каждое описание может быть двух типов: можно узнать длину задуманного учителем натурального числа в некоторой системе счисления или первую цифру этого же числа в некоторой системе счисления. Решить задание - значит найти минимальное натуральное число, подходящее под все описания (оно не обязательно должно совпадать с задуманным числом).
Помогите Тимофею составить программу, определяющую это число. Гарантируется, что ответ не превышает 2 * 109 и все описания для задуманного учителем числа корректны.
Формат входных данных
В первой строке входного файла записано натуральное число n - количество описаний.
В последующих n строках записаны описания. Если описание определяет длину числа в некоторой системе счисления, то первый символ в описании - L (от англ. Length), а если описание определяет первую цифру числа в некоторой системе счисления, то первый символ в описании - D (от англ. Digit). После этого через пробелы указывается основание системы счисления m и результат - натуральное число для длины числа или первая цифра - натуральное число или заглавная буква латинского алфавита, в случае m ≥ 10.
Формат выходных данных
В единственной строке выходного файла запишите одно натуральное число - минимальное из всех чисел, подходящих под все описания, в десятичной системе счисления.
Ограничения
1 ≤ n ≤ 10.
2 ≤ m ≤ 36.
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Подзадача 1: задуманное число не превышает 103, баллы: 30.
Подзадача 2: нет ограничений, но все описания определяют только длину числа в некоторой системе счисления (то есть присутствуют описания только типа L), баллы: 30.
Подзадача 3: нет ограничений, баллы: 40.
Пояснения к примерам
В первом примере: минимальное из чисел, которое в двоичной системе счисления трехзначно, равно 4. Учитель мог задумать любое число из диапазона от 4 до 7.
Во втором примере учитель мог задумать число 2018. Минимальным из чисел, подходящим под все описания, является число 2000.
Тимофей с одноклассниками обожают играть в баскетбол и не пропускают ни одной возможности сыграть в эту замечательную игру. Вот и сегодня на большой перемене состоялась важная игра (за выход в 1/1024 финала Объединенного городского школьного турнира).
Игра начинается со счета 0:0. Каждая результативная атака может принести одной из двух команд 1, 2 или 3 очка.
Введем понятие "ходигры" — последовательность изменения счета на табло. Например, ход игры может быть таким: 0-0, 2-0, 2-1, 5-1, 5-3.
Когда учитель информатики по пути в учительскую заглянул в спортзал, счет на табло был a:b. А после звонка на урок был зафиксирован окончательный результат — счет c:d. Теперь на уроке информатики перед ребятами поставлена задача — определить, сколько существует ходовигры, в которых:
1) Начальный счет — 0:0;
2) Промежуточный счет — a:b;
3) Окончательный счет — c:d.
Помогите Тимофею и его одноклассникам!
Формат входных данных
В первой строке входного файла через пробел записаны два числa: a и b — промежуточный счет. Во второй строке входного файла через пробел записаны два числa: c и d — окончательный счет.
Формат выходных данных
Выведите одно натуральное число — количество различных ходов игры. Гарантируется, что ответ на задачу при любых входных данных не превосходит 1018.
Ограничения
0 ≤ a ≤ c ≤ 20 и 0 ≤ b ≤ d ≤ 20
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
