Задача A1. Два станка ≡

Условие

На производстве имеется два станка. Необходимо изготовить как можно больше деталей за сегодняшнюю смену, продолжительность которой k минут.

Станки находятся в законсервированном состоянии. Для того, чтобы ввести в строй первый станок, требуется a минут, после чего он будет производить x деталей в минуту. Для того, чтобы ввести в строй второй станок, требуется b минут, после чего он будет производить y деталей в минуту.

Для введения в строй станка требуется присутствие инженера, поэтому нельзя вводить в строй два станка одновременно. При этом введение станка в строй и изготовление деталей на другом станке, а также одновременное изготовление деталей на двух станках разрешается.

Требуется выяснить, какое максимальное количество деталей удастся изготовить за k минут.

Формат входных данных

В первой строке ввода дано единственное целое неотрицательное число k — количество минут в смене.

Во второй строке ввода даны целые неотрицательные числа a и x — время введения первого станка в строй и количество деталей, которое он изготавливает за одну минуту.

В третьей строке ввода даны целые неотрицательные числа b и y — время введения второго станка в строй и количество деталей, которое он изготавливает за одну минуту.

Формат выходных данных

Выведите единственное число — максимальное количество деталей, которое удастся изготовить за смену.

Обратите внимание, что ответ в этой задаче может быть довольно большим и не помещаться в 32-битные типы данных. Рекомендуется использовать 64-битный тип данных, например long long в C++ или int64 в Паскале.

Ограничения

0 ≤ k ≤ 10⁹, 0 ≤ a, x ≤ 10⁹, 0 ≤ b, y ≤ 10⁹

Система оценки

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

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

В примере выгодно сначала ввести в строй второй станок и за оставшиеся 15 минут изготовить 45 деталей, а затем ввести в строй первый и за оставшиеся 5 минут изготовить на нём еще 20 деталей.

Если сначала ввести в строй первый станок и изготовить на нем в оставшиеся 10 минут 40 деталей, то после введения в строй второго на нем удастся изготовить лишь 15 деталей, суммарно 55, что меньше, чем 65.

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

20
10 4
5 3

65

Задача A2. Разбиение таблицы ≡

Условие

Рассмотрим таблицу из n строк и m столбцов, в клетки которой по строкам записаны числа от 1 до n ⋅ m. Сначала заполняется первая строка слева направо, затем вторая, и так далее. Другими словами в клетку (r, c) записано число (r − 1) ⋅ m + c.

На рисунке приведен пример такой таблицы для n = 3, m = 5.

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

Формат входных данных

В первой строке ввода задано целое число t — количество запросов.

В следующих t строках заданы по два целых числа n, m.

Формат выходных данных

В t строках выведите ответы на запросы, по одному на строке.

Ответ на каждый запрос должен быть выведен в формате D x, где D — это "V", если нужно резать по вертикали, "H" — если по горизонтали, а x — номер столбца или строки, перед которым надо сделать разрез. Строки пронумерованы от 1 до n, столбцы пронумерованы от 1 до m.

Если правильных ответов несколько, то надо вывести вариант с вертикальным разрезом, если он есть, а если и после этого вариантов несколько, то из вариантов с различными x следует выбрать тот, в котором x меньше.

Ограничения

1 ≤ t ≤ 10⁵, (1 ≤ n, m ≤ 10⁹, 2 ≤ n ⋅ m ≤ 10⁹)

Система оценки

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

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

5
1 3
4 7
1 10
3 3
3 5

V 3
V 5
V 8
H 3
V 4

Задача A3. Изменённая ДНК ≡

Условие

Биологи обнаружили новый живой организм и решили изучить его ДНК. ДНК кодируется последовательностью символов "A", "G", "C" и "T".

Так как строка, кодирующая ДНК, часто очень длинная, для её хранения применяют RLE-кодирование. А именно, каждый блок, состоящий из двух или более идущих подряд одинаковых символов, заменяется на число, равное длине этого блока, после которого записывается соответствующий символ. Например, последовательность "AAAGGTCCA" в закодированной форме имеет вид "3A2GT2CA".

В результате экспериментов, проводимых в лаборатории, ДНК может мутировать. Каждая мутация — это либо удаление одного символа из последовательности, либо добавление одного символа, либо замена одного символа на другой.

Уходя вечером из лаборатории, учёный записал ДНК в закодированной форме. Когда он вернулся на работу утром, он обнаружил, что в ДНК произошла ровно одна мутация. Теперь ученых интересует, какая минимальная и максимальная длина может получиться у новой ДНК в закодированной форме.

Требуется по заданной ДНК в закодированной форме определить, какая мутация может привести к тому, что у новой ДНК будет закодированная форма минимальной возможной длины, а какая — к тому, что у новой ДНК будет закодированная форма максимальной возможной длины.

Формат входных данных

В единственной строке входа находится строка s, состоящая из цифр и букв "A", "G", "C" и "T" — закодированная ДНК.

Гарантируется, что это строка является корректной закодированной записью некоторой строки из символов "A", "G", "C" и "T".

Формат выходных данных

В первой строке выведите мутацию, после которой закодированная строка имеет минимальную длину. Выведите:

• 1 x Z, если надо вставить символ Z так, чтобы слева от него было ровно x старых символов. Символ Z должен быть из множества {A, C, G, T}.
• 2 x, если надо удалить символ с номером x из последовательности.
• 3 x Z, если надо заменить символ с номером x на символ Z. Символ Z должен быть из множества {A, C, G, T}. При этом на этом месте до мутации обязательно должен был находиться символ, не равный Z.

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

Если подходящих ответов несколько, можно вывести любой из них.

Ограничения

Обозначим за n длину закодированной строки, а за L длину исходной строки.

1 ≤ n ≤ 10⁵, 1 ≤ L ≤ 10⁹

Система оценки

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

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

Исходная последовательность имела вид "AAAAACAAAAACC".

Первая операция превращает её в последовательность "AAAAAAAAAAACC", которая кодируется как "11A2C". Эта закодированная последовательность имеет минимальную возможную для этого теста длину, равную 5.

Вторая операция превращает её в последовательность "AACAAACAAAAACC", которая кодируется как "2AC3AC5A2C". Эта закодированная последовательность имеет максимальную возможную для этого теста длину, равную 10.

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

5AC5A2C

3 6 A
1 2 C

Задача A4. Антенна ≡

Условие

Для связи с Землёй членам экспедиции на Марс необходимо собрать антенну. Антенна в разобранном состоянии представляет собой n фрагментов, i-й фрагмент представляет собой штангу длиной s_i сантиметров, на которой закреплены m_i перекладин. Каждый фрагмент содержит хотя бы одну перекладину.

У каждой штанги есть начало, в котором расположен штекер, и конец, в котором расположено гнездо. Любые две штанги можно последовательно соединить, присоединив начало одной к концу другой. Для каждой перекладины известно расстояние от начала её штанги в сантиметрах. Для i-го фрагмента это расстояние может быть от 0 до s_i, значение 0 означает, что перекладина находится непосредственно в начале штанги, значение s_i — что она находится непосредственно в конце штанги. Толщиной перекладин и размерами штекера и гнезда следует пренебречь.

На рисунке показаны три фрагмента антенны из первого примера и отмечены расстояния от начала штанги до перекладины.

Чтобы корректно собрать антенну, необходимо соединить в некотором порядке все n фрагментов, при этом расстояние между любыми двумя соседними перекладинами должно быть одинаковым.

На рисунке показан корректный способ соединить фрагменты в первом примере.

К сожалению, члены экспедиции забыли инструкцию по сборке антенны на Земле, а передать её на Марс не представляется возможным — ведь антенна ещё не собрана. Помогите исследователям!

Требуется определить, в каком порядке необходимо соединить фрагменты антенны, чтобы установить связь с Землей.

Формат входных данных

В первой строке дано одно число n — количество фрагментов.

Далее дано описание n фрагментов. В первой строке описания фрагмента даны два целых числа m_i и s_i — количество перекладин и длина штанги в i-м фрагменте. В следующей строке даны m_i целых чисел p_{i, j} — позиции перекладин, p_{i, j} равно расстоянию в сантиметрах от начала штанги до j-й перекладины на ней.

Формат выходных данных

Если собрать антенну указанным образом возможно, в первой строке выведите Yes, а во второй строке выведите перестановку чисел от 1 до n — номера фрагментов в порядке, в котором их следует соединить, начало каждого следующего фрагмента в этом порядке присоединяется к концу предыдущего фрагмента. Если существует несколько подходящих ответов, можно вывести любой из них.

Если собрать антенну невозможно, в единственной строке выведите No.

Ограничения

1 ≤ n ≤ 100 000, 1 ≤ m_i ≤ 100 000, 0 ≤ s_i ≤ 10⁹

0 ≤ p_{i, 1} < p_{i, 2} < …  < p_{i, mi} ≤ s_i

Сумма всех m_i не превышает 100 000.

Система оценки

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

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

3
1 7
3
1 8
6
2 8
1 6

Yes
2 1 3 

1
1 7
5

Yes
1

1
3 10
2 5 9

No

3
1 5
3
1 3
3
1 6
3

No

4
1 5
0
1 0
0
1 3
3
1 0
0

Yes
3 2 4 1 

Задача B1. Календарь на Альфе Центавра ≡

Условие

На планете в системе Альфы Центавра год состоит из m месяцев, пронумерованных от 1 до m, а каждый месяц из d дней, пронумерованных от 1 до d. В свою очередь, неделя у поселенцев на этой планете состоит из w дней, проиндексированных строчными английскими буквами, от "a" до w-й буквы английского алфавита.

Первый день первого месяца первого года соответствует букве "a".

Требуется определить, какой букве будет соответствовать i-й день j-го месяца k-го года.

Формат входных данных

Первая строка ввода содержит три целых числа d, m и w.

Вторая строка ввода содержит три целых числа i, j и k.

Формат выходных данных

Выведите одну строчную букву английского алфавита — какой букве соответствует i-й день j-го месяца k-го года.

Ограничения

1 ≤ d, m ≤ 100, 1 ≤ w ≤ 26

1 ≤ i ≤ d, 1 ≤ j ≤ m, 1 ≤ k ≤ 10⁹

Система оценки

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

Замечание

Обратите внимание, при решении этой задачи рекомендуется использовать 64-битные типы данных, например long long в C++, int64 в Паскале.

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

30 12 7
18 1 2021

b

Задача B2. Числа ≡

Условие

Аня любит, когда числа состоят из одинаковых цифр. Поэтому ей нравятся числа 777 или 5555, а вот число 1234 ей совсем не нравится.

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

У Ани есть число x. Аня хочет найти минимальное целое число y ≥ x, которое ей понравится.

Требуется написать программу, которая по заданному целому числу x и информации, хорошее ли настроение у Ани, находит минимальное целое число y ≥ x, которое нравится Ане.

Формат входных данных

Первая строка ввода содержит целое число x (обратите внимание, что число x не может быть сохранено в стандартном 32-битном типе данных, необходимо использовать 64-битный тип данных, например long long в C++, int64 в Паскале).

Вторая строка ввода содержит число k, равное 0 или 1. Значение k = 1 означает, что у Ани хорошее настроение, а значение k = 0 — что это не так.

Формат выходных данных

Следует вывести одно целое число y.

Должны выполняться следующие свойства:

• y ≥ x;
• если k = 0, то все цифры в десятичной записи числа y должны совпадать;
• если k = 1, то все цифры в десятичной записи числа y, кроме, может быть, одной, должны совпадать.

Ограничения

1 ≤ x ≤ 10¹⁷

Система оценки

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

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

700
0

777

700
1

700

Задача B3. Хорошие раскраски ≡

Условие

Назовем раскраску клеток таблицы n × m хорошей, если никакие четыре клетки, центры которых образуют вершины прямоугольника со сторонами, параллельными осям координат, не покрашены в один цвет.

Иначе говоря, для раскраски не должно быть такой четверки целых чисел x₁, x₂, y₁, y₂, что 1 ≤ x₁ < x₂ ≤ n, 1 ≤ y₁ < y₂ ≤ m, и клетки (x₁, y₁), (x₂, y₁), (x₁, y₂) и (x₂, y₂) покрашены в одинаковый цвет.

Требуется написать программу, которая по заданным целым числам n, m и c находит любую хорошую раскраску таблицы n × m в c цветов.

Формат входных данных

В первой строке записаны три целых числа n, m, c.

Гарантируется, что для заданных во входных данных значений существует хотя бы одна хорошая раскраска.

Формат выходных данных

Выведите n строк по m чисел в каждой.

В качестве j-го числа i-й строки выведите a_i,j — цвет клетки (i,j) (1 ≤ a_i,j ≤ c).

Если есть несколько хороших раскрасок, можно вывести любую из них.

Ограничения

2 ≤ n, m ≤ 10, 2 ≤ c ≤ 3

Система оценки

Кроме теста из примера в этой задаче 20 тестов, каждый независимо оценивается в 5 баллов. Среди этих тестов в пяти тестах c = 2 и в пятнадцати тестах c = 3.

Для каждого теста сообщается результат проверки на этом тесте.

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

2 2 2

1 2 
2 2 

Задача B4. A+B ≡

Условие

Рассмотрим a, b и c — целые неотрицательные числа, записанные в десятичной системе счисления. Пусть они имеют одинаковую длину n, при этом запись может начинаться с нуля. Числа записаны одно под другим, цифры расположены в три строки и n столбцов. Рассмотрим пример такой записи:

  01211
  12099
  23300
  

Требуется переставить столбцы в этой записи таким образом, чтобы выполнялось равенство a + b = c. В полученной записи ведущие нули уже запрещены. Сколько существует различных способов это сделать?

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

Поскольку ответ может быть довольно большим, требуется посчитать для него остаток по модулю 10⁹ + 7.

Формат входных данных

Во входных данных записаны целые неотрицательные числа a, b и c по одному в строке. Каждое число состоит из n десятичных цифр и может начинаться с нуля.

Формат выходных данных

Выведите количество подходящих перестановок столбцов по модулю 10⁹ + 7.

Ограничения

2 ≤ n ≤ 2 ⋅ 10⁵

Система оценки

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

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

В первом примере подходят все перестановки столбцов.

Во втором примере единственная подходящая перестановка — 10 + 20 = 30. 01 + 02 = 03 не считается из-за наличия ведущих нулей.

В третьем примере возможны варианты 10121 + 21909 = 32030 и 12101 + 20919 = 33020, причём каждый из них может быть получен двумя разными перестановками.

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

123
123
246

6

01
02
03

1

01211
12099
23300

4

121
214
999

0

Задача C0. Дерево ≡

Условие

Дан неориентированный граф. Проверьте, является ли он деревом.

Формат входного файла

В первой строке входного файла заданы через пробел два целых числа n и m — количество вершин и рёбер в графе, соответственно. В следующих m строках заданы рёбра; i-я из этих строк содержит два целых числа u_i и v_i через пробел — номера концов i-го ребра. Граф не содержит петель и кратных рёбер.

Формат выходного файла

В первой строке выходного файла выведите YES, если граф является деревом, и NO в противном случае.

Ограничения

1 ≤ n ≤ 10⁵

0 ≤ m ≤ 10⁵

1 ≤ u_i, v_i ≤ n

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

3 2
1 2
1 3

YES

3 3
1 2
2 3
3 1

NO

Задача C1. Заморозки в Невеции ≡

Условие

Точки города Невеция связаны водными каналами, i-й из которых имеет ширину w_i. Каналы спроектированы так, что из любой точки города можно на лодке попасть в любую другую. Лодка может проплыть по каналу, если её ширина не превосходит ширины канала.

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

Транспортной компании Невеции необходимо знать, через сколько дней их лодки шириной W потеряют возможность попасть из любой точки города в любую другую.

Формат входного файла

Входные данные содержат целые числа N, M и W — количество точек города, количество каналов и ширина лодок. Далее следуют M троек целых чисел a_i b_i w_i — точки, которые соединяет канал, и его ширина. Каждый канал описывается ровно один раз.

Формат выходного файла

Выходные данные должны содержать одно целое число.

Ограничения

2 ≤ N ≤ 10³

1 ≤ a_i, b_i ≤ N

1 ≤ M ≤ N(N − 1)2

1 ≤ w_i, W ≤ 10⁹

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

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

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

4 3 5
1 2 15
2 3 11
3 4 20

4

2 1 1
1 2 3

2

3 3 10
1 2 9
1 3 10
2 3 10

1

Задача C2. Скалолаз ≡

Условие

Артем с раннего детства увлекается скалолазанием. Сегодня он решил покорить крупный горный хребет в своем городе.

Горный хребет представлен прямоугольником размером h × w метров. Каждая гора на этом хребте занимает квадрат 1 × 1 метр. Гора с координатами (x; y) имеет высоту h_y,x метров. Чтобы перебираться между горами, Артём использует канат. Для того, чтобы перебраться с горы x,y на гору i,j, длина каната должна быть большей или равной разнице высот двух гор.

Двигаться Артем может только на соседние по горизонтали или вертикали горы.

Артем будет стартовать с самой верхней левой горы. Он хочет узнать, какой минимальной длины нужен канат, чтобы перебраться с левой стороны на правую сторону (в любую точку). Он просит Вас написать программу, которая сообщит ему минимальную длину каната.

Формат входных данных

В первой строке записано два натуральных числа h и w — размеры горного хребта. В следующих h строках записано по w чисел h_{i, j} — высоты гор.

Формат выходных данных

Программа должна вывести одно число — минимальную длину каната, при помощи которого можно перейти с левой на правую сторону.

Ограничения

2 ≤ h, w ≤ 1000

1 ≤ h_{i, j} ≤ 10⁹

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

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

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

3 3
4 9 7
6 8 1
8 1 1

2

Задача C3. Оптимальное удаление ≡

Условие

Дано дерево, состоящее из n вершин. Корнем дерева считается вершина под номером 1. Необходимо удалить одно ребро из дерева (образовав тем самым еще одно дерево с новым корнем) так, чтобы сумма расстояний от корня до всех вершин была минимально возможной. Напишите программу, которая определит эту сумму.

Формат входных данных

В первой строке записано целое число n - количество вершин в дереве.

В следующих n − 1 строках записано по два различных целых числа a_i и b_i - вершины дерева, которые соединены между собой.

Формат выходных данных

Выведите одно целое число - минимально возможную сумму расстояний от корня до всех вершин.

Ограничения

2 ≤ n ≤ 10⁵

1 ≤ a_i, b_i ≤ n

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

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

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

Минимальную сумму расстояний от корня до всех вершин можно получить, удалив ребро между вершинами 4 и 9. Тогда сумма расстояний от корня до всех вершин первого дерева будет 14, а второго (с корнем в вершине 9) 1.

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

10
1 2
1 3
2 4
2 5
3 6
4 9
6 7
6 8
9 10

15

Задача C4. Слон Пахом и разработка RPG ≡

Условие

Слон Пахом создаёт новую RPG, для игры ему потребовался уровень-лабиринт. Лабиринт содержит n × m платформ, n рядов по m платформ. Платформы бывают трёх видов:

1. Коридоры. В зависимости от ориентации обозначаются или символом "-" (находясь на такой платформе можно, пройти только влево или вправо) или "|" (находясь на такой платформе, можно пройти только вверх или вниз).
2. Перекрёстки. Обозначаются символом "+" (можно пройти в любую сторону).
3. Стены. Обозначаются символом "#" (по ним нельзя пройти).

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

Слон Пахом сгенерировал несколько лабиринтов, но теперь начал сомневаться в проходимости этих лабиринтов. Кроме того, Пахом считает, что поворот платформы запутывает игрока, поэтому для он хочет определить, можно ли пройти лабиринт, а если можно, то он хочет найти минимальное количество поворотов платформ, необходимое для прохождения лабиринта.

Слон Пахом не справился с поставленной задачей и просит вас написать программу для определения минимального необходимого количества поворотов платформ для прохождения лабиринта, если лабиринт проходимый.

Формат входных данных

Первая строка входных данных содержит два целых числа n и m. Следующие n строк содержат по m символов каждая — описание лабиринта.

Формат выходных данных

Первая строка выходных данных должна содержать "YES", если лабиринт проходимый, в противном случае "NO".

Если лабиринт проходимый, то следующая строка должна содержать целое число k — минимальное количество поворотов, необходимое для прохождения лабиринта.

Ограничения

1 ≤ n, m ≤ 10³

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

Решения, работающие для n = 1, оцениваются из 30 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

5 5
+++++
+++++
+++++
+++++
+++++

YES
0

1 8
+-------

YES
0

1 8
+------|

NO

5 6
|-----
|-###-
#|---#
####|#
+++#|-

YES
5

1 1
#

NO

Задача D1. Марфа Геннадьевна в столовой ≡

Условие

Однажды Марфа Геннадьевна пришла в столовую. В меню было N блюд. Блюдо с номером i стоит c_i рублей. Для каждого блюда известен также коэффициент сытости блюда — a_i.

Марфа Геннадьевна знает, что для того, чтобы наесться, нужно, чтобы сумма коэффициентов сытости съеденных блюд была не меньше A.

Какие блюда нужно взять в столовой, чтобы наесться и потратить как можно меньше денег? Обратите внимание, что Марфа Геннадьевна может взять более одной порции блюда (любое целое неотрицательное число порций).

Формат входного файла

Входной файл содержит целые числа N A.

Далее следуют N пар целых чисел c_i a_i.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 100

1 ≤ A ≤ 1000

1 ≤ c_i ≤ 500

1 ≤ a_i ≤ 100

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

3 10
2 1
5 4
6 6

11

4 32
1 8
2 4
3 2
4 1

4

Задача D2. Бег по коридору ≡

Условие

Школьник Петя собрал собственный цветной дисплей с разрешением 2 пикселя по вертикали и N пикселей по горизонтали. Каждый пиксель определяется координатами (a, b), где a — номер строки от 1 до 2, а b — номер столбца от 1 до N.

На дисплее с таким разрешением уже можно играть и Петя разрабатывает одну из игр — "Бег по коридору". По правилам игры, каждый пиксель может быть либо свободен, либо занят препятствием, либо занят игроком, либо занят эликсиром. Игрок может перемещаться в один из смежных пикселей, не занятых препятствием (смежными называются пиксели, соседствующие либо в строке, либо в столбце).

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

Изначально игрок находится в пикселе с координатами (1, 1). Цель игры — добраться до N-ого столбца, минимизировав конечный уровень усталости.

Вам необходимо написать программу, которая по заданному плану коридора определит минимальный уровень усталости, с которым можно пройти игру.

Формат входного файла

В первой строке входного файла содержится число N — горизонтальное разрешение дисплея. Далее следует описание игрового поля — пара строк длиной N каждая. Символ "." (точка) соответствует свободному пикселю, символ "#" (решетка) — занятому препятствием, символ "X" (прописная латинская X) — пикселю с эликсиром.

Гарантируется, что первый символ первой строки равен ".", кроме того, последний символ хотя бы одной из двух строк не равен "#".

Гарантируется, что можно добраться до N-ого столбца.

Формат выходного файла

В выходной файл выведите единственное число — минимальный уровень усталости, которого можно достичь, пройдя игру.

Ограничения

2 ≤ N ≤ 100

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

2
..
.#

1

6
....X.
#XXX..

3

Задача D3. Не только динамика! Новые тесты! ≡

Условие

Дан набор a_i из N чисел. Необходимо расположить числа в последовательности a₁, a₂, …, a_N один за другим так, чтобы максимизировать следующую целевую функцию: (a₁ * a₂ + a₂ * a₃ + …  + a_N − 1 * a_N)

Формат входного файла

Входной файл содержит N, за которым следует N чисел a_i.

Формат выходного файла

В выходном файле единственное число - максимальное значение целевой функции.

Ограничения

2 ≤ N ≤ 16

1 ≤ a_i ≤ 10⁶

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

4
9 1 9 2

108