Алгоритмы

Даны три строки, состоящие из строчных латинских букв. С этими строками можно производить следующие операции: либо заменить один символ строки на два таких же символа (например, заменить символ «a» на «aa»), либо, наоборот, заменить два подряд идущих одинаковых символа на один такой же символ.

Необходимо при помощи этих операций сделать все три строки равными какой-то другой общей строке S либо определить, что это сделать невозможно. При этом нужно минимизировать общее количество операций.

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

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

Примеры

№	Входные данные	Выходные данные
1	aaaza aazzaa azzza	aazza
2	xy xxyy yx	IMPOSSIBLE

В игре Cookie Clicker игрок зарабатывает печеньки (cookies), щёлкая мышкой по изображению большой печеньки. Тратя заработанные печеньки, игрок может покупать различные усовершенствования (ферму, фабрику и т. д.), которые также производят дополнительные печеньки.

Рассмотрим упрощённый вариант этой игры. Пусть игрок может сделать один щелчок мышкой в секунду, что приносит ему одну печеньку. Также в любой момент времени игрок может потратить C печенек на покупку фабрики (при этом у игрока должно быть не меньше C печенек, после покупки фабрики количество его печенек моментально уменьшается на C ). Каждая купленная фабрика увеличивает ежесекундное производство печенек на P штук (то есть если у игрока одна фабрика, то он получает 1  + P печенек в секунду, две фабрики — 1  +  2 P печенек, три фабрики — 1  +  3 P печенек и т. д.). Игрок может приобрести неограниченное число фабрик стоимостью C печенек каждая. Фабрика начинает производить дополнительные печеньки сразу же, например, если после какой-то секунды игры у игрока стало C печенек, то игрок может купить фабрику и уже на следующей секунде его производство печенек увеличится на P штук.

Оригинальная игра никогда не заканчивается, но мы будем считать, что целью игры является набрать N печенек. Определите минимальное время, за которое может быть достигнута цель игры.

Входные данные
Программа получает на вход три целых положительных числа, записанных в отдельных строках: С (стоимость фабрики), P (производительность одной фабрики) и N (необходимое количество печенек).

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	50 3 100	75	Через 50 секунд после начала игры у игрока будет 50 печенек, и он сможет купить фабрику. После этого он будет получать 4 печеньки в секунду, и на производство 100 печенек понадобится еще 25 секунд.
2	99 10 100	100	Игрок сможет набрать 100 печенек за 100 секунд, при этом фабрику покупать нет смысла.

Популярность окружной олимпиады по информатике растет год от года. При этом организаторы должны заранее распечатать как условия задач, так и другие материалы олимпиады (анкеты, памятки и т.п). В этом году они оценили объем печатной продукции в N листов.

Фирма, готовая размножить печатные материалы, предлагает следующие финансовые условия. Один лист она печатает за A1 рублей, 10 листов — за A2 рублей, 100 листов — за A3 рублей, 1000 листов — за A4 рублей, 10 000 листов — за A5 рублей, 100 000 листов — за A6 рублей и 1 000 000 листов — за A7 рублей. При этом не гарантируется, что один лист в более крупном заказе обойдется дешевле, чем в более мелком. И даже может оказаться, что для любой партии будет выгодно воспользоваться тарифом для одного листа.

Печать конкретного заказа производится или путем комбинации нескольких тарифов, или путем заказа более крупной партии. Например, 980 листов можно распечатать, заказав печать 9 партий по 100 листов плюс 8 партий по 10 листов, сделав 98 заказов по 10 листов, 980 заказов по 1 листу или заказав печать 1000 (или даже 10 000 и более) листов, если это окажется выгоднее.

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

Входные данные
На вход программе сначала подается число N (1 ≤ N ≤ 2 × 109) — количество листов в заказе. В следующих 7 строках ввода находятся натуральные числа A1, A2, A3, A4, A5, A6, A7 соответственно (1 ≤ Ai ≤ 106).

Выходные данные
Выведите одно число — минимальную сумму денег в рублях, которая нужна для выполнения заказа. Гарантируется, что правильный ответ не будет превышать 2 × 10⁹.
 

Примеры

№	Входные данные	Выходные данные
1	980 1 9 90 900 1000 10000 10000	882
2	980 1 10 100 1000 900 10000 10000	900

Вася изготовил карточки, написав на них N первых заглавных букв латинского алфавита. Карточки Вася положил в стопку.

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

После этого оказалось, что карточки лежат строго по алфавиту, если просматривать их сверху вниз.

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

Входные данные
Вводится натуральное число N (N не превышает 26).

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

Примеры

№	Входные данные	Выходные данные
1	3	BCA
2	6	CDBEAF

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

Входные данные
Вводится сначала K — вес предмета, который положили на левую чашу (1≤K≤50). Далее записано общее количество гирек N (1≤N≤10). Далее записано N различных натуральных чисел, не превышающих 50, — веса гирек.

Выходные данные
В первой строке выведите веса гирек, которые нужно поместить на левую чашу весов, во второй строке — гирьки, которые нужно поместить на правую чашу. Если на какую-то чашу ни одной гирьки помещать не нужно — выведите в этой строке число 0. Если с помощью данных гирек привести весы в равновесие нельзя, выведите одно число –1. Если вариантов несколько, выведите любой из них.
 

Примеры

№	Входные данные	Выходные данные
1	5 2 3 5	0 5
2	5 3 6 3 4	4 3 6
3	5 1 2	-1

Перед началом тараканьих бегов всем болельщикам было предложено сделать по две ставки на результаты бегов. Каждая ставка имеет вид "Таракан №A придет раньше, чем таракан №B".

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

Входные данные
В первой строке входных данных содержатся два разделенных пробелом натуральных числа: число K, не превосходящее 10, - количество тараканов и число N, не превосходящее 100, - количество болельщиков. Все тараканы пронумерованы числами от 1 до K. Каждая из следующих N строк содержит 4 натуральных числа A, B, C, D, не превосходящих K, разделенных пробелами. Они соответствуют ставкам болельщика "Таракан №A придет раньше, чем таракан №B" и "Таракан №C придет раньше, чем таракан №D".

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

Если требуемого результата добиться нельзя, выведите одно число 0.

Примеры

№	Входные данные	Выходные данные
1	3 2 2 1 2 3 1 2 3 2	3 2 1
2	3 4 1 2 1 3 1 2 3 1 1 2 2 3 1 2 3 2	0

Примечание: Решения задачи на языке программирования Python не проходят ограничения по времени.

Фирма NNN решила транслировать свой рекламный ролик в супермаркете XXX. Однако денег, запланированных на рекламную кампанию, хватило лишь на две трансляции ролика в течение одного рабочего дня.

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

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

Если трансляция ролика включается, например, в момент времени 10, то покупатели, пришедшие в супермаркет в момент времени 10 (или раньше) и уходящие из супермаркета в момент 15 (или позднее) успеют его прослушать целиком, а, например, покупатель, пришедший в момент времени 11, равно как и покупатель, уходящий в момент 14 - не успеют. Если покупатель успевает услышать только конец первой трансляции ролика (не сначала) и начало второй трансляции (не до конца), то считается, что он не услышал объявления. Если покупатель успевает услышать обе трансляции ролика, то при подсчете числа людей, прослушавших ролик, он все равно учитывается всего один раз (фирме важно именно количество различных людей, услышавших ролик).

Входные данные
В первой строке входного файла вводится  число N - количество покупателей (1<=N<=2000). В следующих N строках записано по паре натуральных чисел - время прихода и время ухода каждого из них. Все значения времени - натуральные числа, не превышающие 10⁹. Время ухода человека из супермаркета всегда строго больше времени его прихода в супермаркет.

Выходные данные
Выведите  через пробел три числа: количество покупателей, которые прослушают ролик целиком от начала до конца хотя бы один раз, и моменты времени, когда должна начинаться трансляция ролика. Моменты времени должны быть выведены в возрастающем порядке и должны быть натуральными числами, не превышающими 2·10⁹. Если вариантов ответа несколько, выведите любой из них.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 11 1 3 6 15 1 6	3 1 6	Трансляция роликов начинается в моменты времени 1 и 6. Первое объявление успевают прослушать покупатели номер 1 и 4, второе - 1 и 3. Когда бы ни начиналась трансляция объявления, 2-й покупатель не сможет его прослушать, так как находится в супермаркете менее 5 минут. Приведенный ответ является не единственным верным ответом на этот тест.
2	1 1 10	1 3 25	Объявление, трансляция которого начинается в момент 3, единственный покупатель обязательно услышит. Вторую трансляцию (раз она оплачена) мы можем сделать когда угодно, например, в 25 минут в пустом супермаркете (впрочем, мы не можем начать трансляцию второго объявления, например, в момент 7 - т.к. к этому моменту еще не закончится первая трансляция)
3	3 1 10 11 20 21 30	2 1 22	Объявление услышат лишь 2 из 3-х покупателей.

Как известно, не только люди любят принимать участие в различных соревнованиях. Среди рыб и моллюсков также проводится множество состязаний на дне океана. Акула Семён участвует в самом престижном соревновании Мирового океана на звание самой опасной акулы. Во время этого состязания акулы соревнуются в различных дисциплинах: плавание на скорость, маскировка, навигация по картам и многим другим. Сейчас Семён проходит испытание под названием «разрушение».

Во время этого испытания перед акулой ставят m доминошек. Все доминошки стоят на одной прямой, однако высоты доминошек могут различаться. Расстояние между соседними доминошками равно 1. Кроме того, у каждой доминошки есть своя стоимость, выраженная целым числом. Цель акулы — уронить все доминошки. Для этого акула может толкнуть любую доминошку влево или вправо, после чего она начнёт падать в этом направлении. Если во время падения доминошка задевает другие, они также начинают падать в ту же сторону, в которую падала исходная, таким образом начинается цепная реакция, в результате которой может упасть множество доминошек. Падающая доминошка задевает другую, если и только если расстояние между ними строго меньше высоты падающей доминошки, причем доминошки не обязательно должны быть соседними.

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

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

Входные данные
Для уменьшения размера ввода высоты и стоимости доминошек задаются при помощи блоков.

В первой строке заданы два целых числа n и m (1 ≤ n≤ 250 000, 1 ≤ m ≤ 10⁷ ) — количество блоков и суммарное количество доминошек, которые надо уронить Семёну, соответственно.

Затем следует описание n блоков. Описание каждого блока состоит из трёх строк.

В первой строке описания блока с номером i содержится целое число k_i (1 ≤ k_i ≤ 250000, \(\sum_{i=1}^n {k_i ? 250 000}\) ) — количество доминошек в блоке.

Во второй строке описания блока с номером i содержатся ki целых чисел a_i,j (1 ≤ a_i,j ≤ m) — высоты доминошек в блоке.

В третьей строке описания блока с номером i содержатся ki целых чисел c_i,j (1 ≤ c_i,j ≤ 100000) — стоимости доминошек в блоке.

Далее следует описание последовательности доминошек, которые надо уронить Семёну, в порядке слева направо.

В первой строке описания последовательности задано целое число q (n ≤ q ≤ 250000) — количество блоков в последовательности доминошек, которые надо уронить.

В следующих q строках содержатся пары целых чисел id_i mul_i (1 ≤ id_i ≤ n, 1 ≤ mul_i ≤ 100000), обозначающие, что очередные k_idi в порядке слева направо доминошек — это доминошки блока id_i, чьи стоимости были умножены на число mul_i.

Гарантируется, что \(\sum_{i=1} ^q k_{id_i} = m\) , а также, что каждый блок встречается хотя бы один раз в последовательности доминошек, которые требуется уронить, то есть для всех i от 1 до n найдется j такое, что id_j=i.

Выходные данные
Выведите одно целое число — минимальную суммарную стоимость доминошек, которые надо толкнуть, чтобы все доминошки упали.

Примечание
В первом примере перед Семёном стоят 7 доминошек. Их высоты равны [3122122] , а стоимости равны [4363121] . Сначала Семёну следует уронить доминошку с номером 7 влево, она упадёт и заденет доминошку с номером 6. Доминошка 6, падая, заденет доминошку с номером 5, которая упадёт, но не заденет другие доминошки. Затем Семён должен уронить доминошку с номером 1 вправо, она, падая, заденет доминошки с номерами 2 и 3, а доминошка 3, падая, заденет доминошку 4, таким образом все доминошки упадут.

Во втором примере перед Семёном стоит одна доминошка стоимостью 10000000000.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 7 3 1 2 2 1 2 1 1 3 2 3 2 2 1 3 1 1	5	Перед Семёном стоят 7 доминошек. Их высоты равны [3122122] , а стоимости равны [4363121] . Сначала Семёну следует уронить доминошку с номером 7 влево, она упадёт и заденет доминошку с номером 6. Доминошка 6, падая, заденет доминошку с номером 5, которая упадёт, но не заденет другие доминошки. Затем Семён должен уронить доминошку с номером 1 вправо, она, падая, заденет доминошки с номерами 2 и 3, а доминошка 3, падая, заденет доминошку 4, таким образом все доминошки упадут.
2	1 1 1 1 100000 1 1 100000	10000000000	Перед Семёном стоит одна доминошка стоимостью 10000000000

Рома и Денис отправились на соревнование по программированию. В долгой дороге ребята вспоминали операции над строками. Денис сказал, что в Python строки можно умножать на число, тогда Рома, программирующий на С++, решил придумать операцию перемножения строк. По версии Ромы, умножение строки s длины n на строку t обозначается как s·t и равно строке t+s₁+t+s₂+...+t+s_n+t, где s_i обозначает i-й символ строки s, а знаком « + » обозначено сложение (конкатенация) строк. Например, произведением строк « abc » и « de » является строка « deadebdecde », а произведением строк « z » и « ab » является строка « abzab ». Обратите внимание, что, в отличие от умножения чисел, произведение строк s и t, вообще говоря, не равно произведению строк t и s.

Денис решил продолжить мысль Ромы — он, как ценитель прекрасного, решил определить красоту строки как максимальную длину подряд идущей группы одинаковых букв. Например, красота строки « xayyaaabca » равна 3, так как самая длинная группа подряд идущих одинаковых букв — это « aaa », а красота строки « qwerqwer » равна 1, потому что все соседние буквы в ней различны.

Чтобы развлечь Дениса, Рома написал ему на листочке n строк p₁,p₂, p₃, ... ,p_n и попросил его вычислить красоту строки (...((p₁·p₂)·p₃)·...)p_n. Денис не до конца понял, как работает умножение Ромы, но не хочет признаваться в этом, поэтому просит посчитать красоту этой строки вас. Рома знает, что Денис слишком впечатлительный, поэтому гарантирует, что красота полученной строки не превосходит 10⁹.

Входные данные
В первой строке содержится число n (1 ≤ n ≤ 100000) — количество строк, которые написал Рома.

В следующих n строках содержатся непустые строки p₁, p₂, ..., p_n, состоящие из маленьких букв английского алфавита.

Гарантируется, что суммарная длина строк не превосходит 100000, а также, что красота произведения всех строк не превосходит 10⁹.

Выходные данные
Выведите одно целое число — красоту произведения строк.
 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 a b a	3	произведение трёх строк равно « abaaaba »
2	2 bnn a	1	произведение двух строк равно « abanana »

У ковбоя Влада день рождения! На праздник собрались n детей. Чтобы поздравить ковбоя, дети решили водить вокруг Влада хоровод. Среди детей, пришедших к Владу, есть и высокие, и низкие, поэтому если они встанут в хороводе как угодно, многим из них может быть неудобно, потому что если в хороводе рядом стоят очень высокий и очень низкий ребёнок, им трудно держаться за руки. Поэтому дети решили встать в хоровод так, чтобы максимальная разность ростов двух соседних детей была минимальной.

Более формально, пусть n детей выстроились в хоровод. Пронумеруем их целыми числами от 1 до n так, чтобы справа от ребёнка с номером i стоял ребёнок с номером i+1, а справа от ребёнка с номером n стоял ребёнок с номером 1. Тогда неудобством этого хоровода назовём максимальную разность между ростом детей, которые стоят рядом. Обратите внимание, что разностью в росте двух детей называется разность между ростом более высокого и более низкого ребёнка, таким образом, разность в росте двух детей всегда неотрицательна.

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

Входные данные
В первой строке содержится одно целое число n (2 ≤ n≤ 10⁵) — количество детей, которые пришли на день рождения ковбоя Влада.

Во второй строке заданы n целых чисел a_i (1≤a_i≤10⁹) — рост каждого из детей. Рост детей задан в нанометрах и уменьшен на 10⁹, таким образом, рост ребёнка с a_i=1 чуть выше метра, а рост ребёнка с a_i=10⁹ составляет два метра.

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

Примеры

№	Входные данные	Выходные данные	Пояснения
1	5 2 1 1 3 2	1 2 3 2 1	Здесь неудобство хоровода равно 1, так как разность в росте между соседними детьми равна 1, 1, 1, 1 и 0 соответственно. Обратите внимание, что последовательности [23211] , [32112]  задают те же хороводы и отличаются только выбором ребёнка с номером 1.
2	3 30 10 20	10 30 20	Неудобство хоровода равно 20, так как разность в росте детей высотой 10 и 30 равна 20.

У Карлсона дома есть набор из n банок с конфетами. Банки пронумерованы от 1 до n , в i -й из них лежит a i конфет. Карлсон считает набор банок симпатичным , если в этом наборе нет трех банок с разным числом конфет.

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

Входные данные
Первая строка входных данных содержит натуральное число n ( 1 ≤ n ≤ 10⁵ ) — количество банок в наборе Карлсона.

Вторая строка входных данных содержит n целых чисел a_i ( 0 ≤ a_i ≤ 10⁹ ) — число конфет в банках. Соседние числа отделены друг от друга одним пробелом.

Выходные данные
Выведите одно число — минимальное общее количество конфет, которое придется добавить, чтобы Карлсон считал набор банок симпатичным.

Примечание
В первом тесте из примера Карлсон может добавить в первую банку две конфеты, а во вторую банку — одну конфету. Тогда в первой и четвертой банках будет лежать по 7 конфет, а во второй и третьей — по 2 конфеты.

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

Примеры

№	Входные данные	Выходные данные
1	4 5 1 2 7	3
2	3 1 1 1	0

Миша установил на свой телефон новую игру «Мемтест 2к17». В ней предусмотрены ежедневные награды за посещение. Награды бывают n уровней. Тип награды зависит от награды за предыдущий день, а именно:

если игрок в предыдущий день не посещал игру, то за сегодняшнее посещение он получит награду уровня 1;
если игрок в предыдущий день зашёл в игру и получил награду уровня k ( k ≠ n ), то за сегодняшнее посещение он получит награду уровня k + 1 ;
если игрок в предыдущий день зашёл в игру и получил награду уровня n , то за сегодняшнее посещение он получит награду уровня 1.
На Форуме для Крутых Программистов Миша выяснил, что награды каждого из уровней составляют соответственно a 1 , a 2 , ..., a n золотых монет.
Через m дней состоится турнир по «Мемтест 2к17», к которому Миша хочет собрать как можно больше золотых монет. Помогите ему спланировать посещения игры на протяжении m дней, оставшихся до турнира. Найдите наибольшее количество золотых монет, которое он сможет получить за счёт ежедневных наград в этот период. Можно считать, что игра установлена в первый из этих m дней, то есть до этого Миша в неё ни разу не заходил.

Входные данные
Первая строка входных данных содержит натуральные числа n и m ( 1 ≤ n , m ≤ 1000 ) — количества уровней наград и дней до турнира.

Вторая строка входных данных содержит n целых чисел a 1 , a 2 , ..., a n ( 1 ≤ a i ≤ 1000 ), где a i — величина награды i -го уровня в золотых монетах.

Выходные данные
Выведите одно натуральное число — наибольшее количество золотых монет, которое Миша сможет получить до турнира.

Примечание
В первом тесте из примера Мише выгодно заходить в игру каждый день. Тогда он получит 1 + 2 + 4 = 7 золотых монет.

Во втором тесте из примера Мише выгодно заходить в игру в первый и третий день, получив в каждый из них по 4 монеты, тогда в сумме он получит 8 монет.
 

Примеры

№	Входные данные	Выходные данные
1	3 3 1 2 4	7
2	3 3 4 2 1	8

Беда! К городу N приближается метеорит. Людей уже успели эвакуировать, но домам урона не избежать. Ученые уже выяснили, куда упадет метеорит. Вас, как сотрудника страховой компании, попросили выяснить количество домов, которые пострадают при падении метеорита.

Введём на плоскости прямоугольную систему координат. Город представляет собой прямоугольник n × m . Его левый нижний угол расположен в точке с координатами (0, 0) , а правый верхний угол в точке с координатами ( n - 1, m - 1) . В каждой точке с целыми координатами внутри или на границе этого прямоугольника находится дом. Дома в городе N маленькие, поэтому их можно считать точками.

Известно, что метеорит упал в точку ( x , y ) , а радиус его поражения равен r . Таким образом, все дома города на расстоянии не более r от точки падения метеорита получат повреждения. Найдите количество домов, которые получат повреждения.

Входные данные
Первая строка содержит два целых числа n , m ( 1 ≤ n , m ≤ 500 ) — размеры города N.

Вторая строка содержит три целых числа x , y , r ( - 500 ≤ x , y ≤ 500 ; 0 ≤ r ≤ 500 ) — координаты точки падения метеорита и радиус поражения, соответственно.

Выходные данные
Выведите одно число — количество повреждённых домов.

Примечание
Иллюстрация к тесту из примера: чёрными точками обозначены повреждённые дома, белыми — уцелевшие.

Примеры

№	Входные данные	Выходные данные
1	2 3 1 2 1	3

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

К сожалению, первый же квест в игре поставил Петю в тупик. Выполнив задание, он получил n магических артефактов, которые можно использовать для получения золота. Для каждого артефакта известна его ценность , для i -го артефакта она равна w_i . Для получения золота артефакты можно активировать . Каждый артефакт можно активировать только один раз. Петя может активировать артефакты в произвольном порядке.

У героя, которым управляет Петя, есть магическая сила , исходно она равна нулю. Есть два способа активировать артефакт: с помощью магии и с помощью силы. Если активировать артефакт с ценностью w с помощью магии, то магическая сила героя увеличивается на w . Если же активировать артефакт с ценностью w с помощью силы, то герой получает xw золотых монет, где x — магическая сила героя в момент активации артефакта.

Например, если герой Пети получил 4 артефакта с ценностями 1, 1, 2 и 2, то можно получить 9 золотых монет, действуя следующим образом. Сначала надо активировать с помощью магии по одному артефакту с ценностью 1 и 2. После этого магическая сила героя равна 3, теперь можно активировать с помощью силы оставшиеся артефакты и получить 3 и 6 золотых монет, соответственно.

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

Входные данные
Первая строка входных данных содержит единственное число n — количество магических артефактов ( 1 ≤ n ≤ 100 ).

Вторая строка входных данных содержит n чисел w₁ , w₂ , ..., w_n — ценности артефактов ( 1 ≤ w_i ≤ 100 ).

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

Примеры

№	Входные данные	Выходные данные
1	4 1 1 2 2	9

Давным-давно большинство персональных компьютеров были оборудованы видеокартами, работавшими только в текстовом режиме. Если программист хотел изобразить картинку на экране, ему приходилось использовать псевдографику или ASCII-графику. Вот пример картинки, нарисованный с ее помощью:

^..^
(OO)
/  \
()()

Вам дан многоугольник, нарисованный с помощью ASCII-графики. Ваша задача состоит в том, чтобы посчитать количество его сторон.
Картинка состоит из символов ‘.’, ‘\’ и ‘/’. Каждый символ изображает единичный квадрат картинки. Символ ‘.’ обозначает пустой квадрат, символ ‘/’ — квадрат с отрезком из левого нижнего угла в правый верхний, а символ ‘\’ — квадрат с отрезком из левого верхнего угла в правый нижний.


Входные данные
Первая строка входных данных содержит два числа h и w — высота и ширина изображения (2 ? h, w ? 100). Следующие h строк, по w символов в каждой, содержат описание многоугольника, нарисованного с помощью ASCII-графики.
Гарантируется, что картинка содержит ровно один многоугольник, не имеющий самопересечений и самокасаний.

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

Примеры

№	Входные данные	Выходные данные
1	4 4 /\/\ \../ .\.\ ..\/	8

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

Арсений показал расписание своему тренеру, но ему оно не до конца понравилось. Тренер объяснил, что тренироваться в следующий час после приёма пищи вредно для здоровья.

Теперь Арсений хочет изменить свое расписание так, чтобы он ни разу не тренировался непосредственно после еды. При этом он хочет изменить минимальное число пунктов своего расписания. Помогите Арсению!

Входные данные
В первой строке входных данных содержится число n — количество пунктов в расписании Арсения ( 1 ≤ n ≤ 10⁵ ).

Во второй строке содержится исходное расписание Арсения. Это строка s длины n , состоящая только из латинских букв « t » и « e », при этом если на позиции i в строке s стоит буква « t », то это значит, что в i -м часу Арсений запланировал тренироваться, а если на этой позиции стоит буква « e », то это значит, что в i -м часу Арсений запланировал есть.

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

Во второй строке выведите строку из n латинских букв « t » и « e » — изменённое расписание в том же формате, что и во входных данных. Если подходящих расписаний несколько, выведите любое из них.
 

№	Входные данные	Выходные данные
1	6 tttete	1 ttteee
2	5 tttte	0 tttte
3	9 eeeeetttt	4 eeeeeeeee

Пятиклассник Лёня недавно прочитал статью о числах Фибоначчи.

Числами Фибоначчи называется числовая последовательность F₁ , F₂ , ..., F_n , ... , которая устроена следующим образом: F₁ = 1 , F₂ = 2 , а каждое следующие число вычисляется как сумма двух предыдущих: если i ≥ 3 , то F_i = F_i - 1 + F_i - 2 . Последовательность чисел Фибоначчи, таким образом, начинается с чисел 1, 2, 3, 5, 8, 13, 21, ... .

Сегодня Лёня изучает числа Фибоначчи с номерами от L до R , включительно. Так как Лёня очень любит число 3, ему стало интересно, сколько чисел Фибоначчи среди тех, которые он изучает сегодня, делятся на 3. Например, если L = 3 и R = 7 , то Лёня будет изучать числа F₃ = 3 , F₄ = 5 , F₅ = 8 , F₆ = 13 и F₇ = 21 . Среди них на 3 делятся два числа: F₃ = 3 и F₇ = 21 .

Напишите программу, которая поможет Лёне найти ответ на волнующий его вопрос.

Входные данные
Первая строка входных данных содержит число L , а вторая — число R ( 1 ≤ L ≤ R ≤ 10⁵ ).

Выходные данные
Выведите единственное число — количество чисел Фибоначчи с номерами от L до R , включительно, которые делятся на 3.
 

№	Входные данные	Выходные данные
1	3 7	2

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

Улицы в новой столице образуют правильную прямоугольную сетку, в которой все улицы пересекаются ровно через одну местную единицу длины. Вертикально идущие улицы называются улицами, а горизонтально идущие — аллеями. Всего в городе получилось 2000 улиц и 2000 аллей, поэтому, чтобы не придумывать много новых названий, их все просто пронумеровали. Улицы пронумеровали с запада на восток числами от −1000 до 999, а аллеи — с юга на север, тоже числами от −1000 до 999. Центром города считаются кварталы на пересечении улиц и аллей с номерами от −100 до 100.

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

Сколько местных единиц длины придется проезжать мэру новой столицы каждый вечер, возвращаясь из мэрии города домой? И мэрия, и дом мэра находятся в центре города. Мэр едет домой кратчайшим путем, соблюдая, впрочем, правила дорожного движения.

Входные данные
В первой строке даны два числа x1 и y1 — номер улицы и номер аллеи, на пересечении которых находится мэрия. В второй строке даны два числа x2 и y2 — номер улицы и номер аллеи, на пересечении которых находится дом мэра. Все числа целые и не превосходят по модулю 100.

Выходные данные
Выведите одно число: длину кратчайшего пути от мэрии до дома мэра на автомобиле.-
 

Примеры

№	Входные данные	Выходные данные
1	0 0 1 1	4
2	3 5 2 4	4

Начались каникулы, и дядя Фёдор, изрядно соскучившись по своим школьным друзьям, пригласил их всех в гости к себе в Простоквашино. После некоторых раздумий n из них согласились приехать. Взяв с собой все необходимые для отдыха на природе вещи, они приехали на вокзал покупать билеты. Выяснилось, что в поездах, идущих до Простоквашино, есть только купейные вагоны. В каждом вагоне всего k₄ четырехместных купе и k₂ — новых двухместных купе. Кроме друзей дяди Фёдора, никто не хочет ехать в Простоквашино, поэтому все места в поезде пока свободны. Друзья решили, что они хотят поехать все в одном вагоне: вместе ведь веселее. Чтобы поездка запомнилась надолго, один из друзей дяди Фёдора, Женя, решил одолжить у папы фотоаппарат «Зенит» и сфотографировать всех участников поездки, сидящих каждый на своем месте в поезде, по одному снимку на купе. Но пленка дорогая, а проявка — это долго и нудно, поэтому Женя попросил купить билеты так, чтобы вся дружная компания занимала как можно меньше купе. Помогите Жене посчитать, сколько в лучшем случае ему понадобится кадров, чтобы сфотографировать всю компанию, то есть посчитайте, сколько минимально купе они должны занять.

Входные данные
В первой и единственной строке вводятся числа n, k₄ и k₂ — количество друзей дяди Фёдора, едущих в Простоквашино, количество четырехместных купе в вагоне и количество двухместных купе в вагоне соответственно (1≤n≤10¹⁸, 0≤k₄≤10¹⁸, 0≤k₂≤10¹⁸).

Выходные данные
Выведите одно целое число — минимальное количество купе, в которых можно разместить всех друзей дяди Фёдора. Если же разместить всех друзей в одном вагоне не получится, выведите −1.

Примеры

№	Входные данные	Выходные данные
1	10 5 3	3

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

Картофельные поля обычно очень аккуратно устроены: кусты картофеля рассажены на них так, что образуют клетчатое поле, где каждая клетка — картофельный куст. Как только на каком-то из кустов появляется колорадский жук, он начинает активно есть и размножаться. Поэтому каждый час на каждый куст будет добавляться столько же жуков, сколько соседних с ним по стороне кустов, уже зараженных жуками. Например, если у куста ровно один сосед, на котором уже есть жуки, то на него добавится один жук, а если все четыре соседа заражены жуками, то на куст добавится четыре новых жука. И если жуков не остановить, они заполнят собой все поле. Но к счастью, когда-то давно дядя Фёдор, прочитав статью в «Мурзилке», сделал отпугиватель колорадских жуков...

Если честно, Матроскин не очень понял, как работает этот отпугиватель. Но главное он запомнил: его надо установить на один из кустиков картофеля, и как только на этом кустике окажется ровно k колорадских жуков, что-то (вот этого Матроскин и не понял) произойдет и все жуки сбегут с поля.

Зная координаты куста картофеля, на который Матроскин установил отпугиватель, посчитайте, через сколько часов после появления первого колорадского жука на поле он подействует. Матроскин поставил ловушку в первый час после появления жука на поле.

Входные данные
Вам даны три числа: x и y — координаты кустика картофеля, на который Матроскин установил отпугиватель, и k — параметр отпугивателя (1<=k<=10⁹, |x|<=10⁹, |y|<=10⁹  ). Тот из кустов, на котором был найден первый жук, имеет координаты (0, 0) . Координаты всех кустов поля не превосходят 10⁹+1 по модулю.

Выходные данные
Выведите одно целое число: через сколько часов ловушка сработает. Если же ловушка никогда не сработает, выведите −1.

Примеры

№	Входные данные	Выходные данные
1	0 0 1	0
2	0 0 5	2