Алгоритмы

Даны двухчашечные весы и набор гирек. На левую чашу весов положили взвешиваемый предмет весом 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

На координатной плоскости расположены равнобедренный прямоугольный треугольник ABC с длиной катета d и точка X. Катеты треугольника лежат на осях координат, а вершины расположены в точках: A (0,0), B (d,0), C (0,d).

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

Входные данные
Сначала вводится натуральное число d(не превосходящее 1000), а затем координаты точки X – два целых числа из диапазона от ­–1000 до 1000.

Выходные данные
Если точка лежит внутри, на стороне треугольника или совпадает с одной из вершин, то выведите число 0. Если точка лежит вне треугольника, то выведите номер вершины треугольника, к которой она расположена ближе всего (1 – к вершине A, 2 – к B, 3 – к C). Если точка расположена на одинаковом расстоянии от двух вершин, выведите ту вершину, номер которой меньше.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 1 1	0	Точка лежит внутри треугольника.
2	3 -1 -1	1	Точка лежит вне треугольника и ближе всего к ней вершина A
3	4 4 4	2	Точка лежит на равном расстоянии от вершин B и C,в этом случае нужно вывести ту вершину, у которой номер меньше, т.е. выведено должно быть число 2
4	4 2 2	0	Точка лежит на стороне треугольника.

Дано натуральное четырехзначное число. Найдите минимальное натуральное четырехзначное число, состоящее из тех же цифр, что и заданное. Заметим, что четырехзначные числа не могут начинаться с нуля.

Входные данные
Вводится натуральное четырехзначное число.

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

Примеры

№	Входные данные	Выходные данные
1	1513	1135

Перед началом тараканьих бегов всем болельщикам было предложено сделать по две ставки на результаты бегов. Каждая ставка имеет вид "Таракан №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.

В Берляндии плачевная ситуация с междугородним автобусным сообщением. Во всей стране есть всего три автобусных маршрута, по каждому из которых курсирует лишь один автобус. В первый день нового года ровно в полночь все три автобуса отправляются по своим маршрутам из столицы Берляндии. Известно, что первому автобусу на то, чтобы проехать весь маршрут и вернуться в столицу требуется a минут, второму — b минут, а третьему — c минут. Таким образом, первый автобус отправляется из столицы Берляндии в моменты времени 0, a, 2a, 3a , второй — в моменты времени 0, b, 2b, 3b , а третий в моменты времени 0, c, 2c, 3c .

Момент времени называется подходящим для пересадки , если в этот момент все три автобуса отправляются из столицы Берляндии. Например если a=1, b=2, c=1, то моменты времени 0 и 2 являются подходящими для пересадки, а момент времени 1 не является, потому что в этот момент времени второй автобус находится в пути. Берляндия — особая страна с особым измерением времени, поэтому в берляндских сутках ровно t минут. Это означает, что в первый день происходят все моменты времени с 0-го по (t−1)-й включительно, во второй день — c t-го по (2t−1)-й включительно, в третий — с 2t-го по (3t−1)-й включительно и так далее.

Министерство транспорта Берляндии заинтересовалось, сколько подходящих для пересадки моментов времени произойдёт в d-й день в Берляндии. К сожалению, местные чиновники заняты другими делами, поэтому ответить на этот вопрос было поручено вам.

Входные данные
В пяти строках заданы пять целых чисел a, b, c, t  и d (1≤a, b, c≤10⁶ , 1≤t, d≤10⁹ ) — время полного прохождения маршрута первым, вторым и третьим автобусами, соответственно, количество минут в сутках и номер дня, которым интересуется министерство транспорта Берляндии.

Выходные данные
Выведите одно целое число — количество подходящих для пересадки моментов времени в d-й день.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	1 2 1 3 1	2	Сутки длятся 3 минуты, поэтому все моменты времени в день с номером 1 — это 0, 1, 2, из них моменты времени 0 и 2 являются подходящими для пересадки
2	2 3 4 7 2	1	Здесь рассматриваются вторые сутки с моментами времени 7, 8, 9, 10, 11, 12, 13. Первый автобус отправляется в моменты времени 8, 10, 12, второй автобус — в моменты времени 9 и 12, а третий — в моменты времени 8 и 12. Таким образом, только момент времени 12 является подходящим для пересадки.
3	2 3 4 3 3	0	Нет ни одного подходящего для пересадки момента времени

У Карлсона дома есть набор из 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

На Марсе есть большой полигон для испытания роботов. Он представляет собой таблицу из n строк и m столбцов, столбцы которой направлены с севера на юг, а строки — с запада на восток. В каждой клетке таблицы находится ускоритель, направленный в одну из сторон света.

Находясь в клетке, робот может воспользоваться ускорителем в ней. При этом он попадает в соседнюю с текущей клетку в направлении ускорителя и не тратит топливо. Если соседней клетки в направлении ускорителя нет, то им нельзя воспользоваться. Также робот может не пользоваться ускорителем и переместиться в любую из соседних клеток, затратив один литр топлива.

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

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


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

Следующие n строк содержат по m латинских букв, описывающих направления ускорителей в очередной строке. Буква соответствуют направлению ускорителя: N — на север, W — на запад, S — на юг, E — на восток. Строки занумерованы с севера на юг, а столбцы с запада на восток. Таким образом, направление на север соответствует уменьшению номера строки, направление на юг — увеличению номера строки, направление на запад — уменьшению номера столбца, а направление на восток — увеличению номера столбца.

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

 

Примеры

№	Входные данные	Выходные данные
1	5 3 SSN NSN SWN SWE ENS	2

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

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

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


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

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

Примеры

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

Маше на день рождения подарили набор матрёшек!

Теперь Маша сидит и вкладывает их одну в другую. Она заметила, что матрёшки отличаются по размеру, и одна помещается внутри другой, только если ее размеры строго меньше. Так, если есть две матрёшки i и j , а их размеры a_i и a_j соответственно, то матрёшка i вкладывается внутрь матрёшки j тогда и только тогда, когда a_i < a_j . Разумеется, непосредственно внутрь матрёшки можно вложить только одну другую матрёшку, иначе получится неаккуратно, а Маша — очень аккуратная девочка.

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

Входные данные
В первой строке находится число n — количество матрёшек, подаренных Маше ( 1 ≤ n ≤ 1000 ). В следующей строке через пробел находятся n чисел — размеры матрёшек. Число a_i , стоящее на месте i , задает размер матрёшки с номером i ( 1 ≤ a_i ≤ 10 000 ).

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

Примеры

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

Арсений — молодой перспективный спортсмен. Всё, что любит делать Арсений — это тренироваться и вкусно есть. Также он отличается пунктуальностью. Только что он составил расписание из 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

На Марсе используют систему счисления с основанием k . В отличие от привычной нам десятичной системы счисления, в этой системе счисления k цифр со значениями от 0 до k - 1 , а вес цифры в i -м разряде равен k_i .

Например, пусть k = 8 . Запись 357₈ означает число 3·8 2 + 5·8 + 7 , в более привычной землянам десятичной системе счисления это число записывается как 239₁₀ . А число 192₁₀ , в системе счисления с основанием 8 записывается как 300₈ .

Ильдар — юный марсианин, и он очень любит круглые числа. Ильдар называет число достаточно круглым , если его запись в системе счисления с основанием k заканчивается хотя бы на n нулей. Сегодня Ильдар хочет найти i -е по порядку достаточно круглое число.

Помогите Ильдару, найдите i -е достаточно круглое в системе счисления с основанием k натуральное число и выведите его в десятичной системе счисления. Ильдар очень дружелюбен и гарантирует, что ответ в десятичной системе счисления не превосходит 10¹⁸ .

Входные данные
Все ограничения на числа в этой задаче заданы в десятичной системе счисления. Все числа во вводе также записаны в десятичной системе счисления.

Первая строка входных данных содержит число k — основание системы счисления, которую использует Ильдар ( 2 ≤ k ≤ 10⁹ ).

Вторая строка входных данных содержит число n — минимальное количество нулей на конце достаточно круглого числа ( 0 ≤ n ≤ 100 ).

Третья строка входных данных содержит число i — порядковый номер достаточно круглого числа, которое интересует Ильдара ( 1 ≤ i ≤ 10⁹ ).

Выходные данные
Выведите одно число — запись в десятичной счистеме счисления i -го по порядку достаточно круглого в системе счисления с основанием k натурального числа. Гарантируется, что ответ не превышает 10¹⁸ .

Обратите внимание, что ответ может не поместиться в стандартный 32-битный тип данных. Надо использовать 64-битный тип, в паскале он называется « int64 », в C++ « long long », в Java « long ». Если вы пишете на языке Python, то волноваться не надо, в Python встроенный целочисленный тип не имеет ограничений на величину числа.
 

№	Входные данные	Выходные данные
1	8 2 2	192

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

Числами Фибоначчи называется числовая последовательность 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

В этой задаче мы снова возвращаемся в младшую группу детского сада «Телепузики». Чтобы окончательно успокоить детей, воспитательница решила включить им мультик про Тома и Джерри. Серия, которую сейчас смотрят дети, довольно-таки незамысловата — в ней Джерри развесил по потолку комнаты наковальни на веревках. Когда Том оказывается под очередной наковальней, Джерри перерезает веревку. Наковальня падает на Тома, Тому больно, всем остальным весело, дети смеются. В общем, вполне обычная серия.

А вам нужно по кадру из этой серии определить, упадет ли наковальня на Тома, если Джерри перережет веревку.

Входные данные
Вам дана ASCII-арт картинка, то есть картинка, нарисованная символами. На ней есть наковальня, привязанная веревкой к потолку, и кот Том. В первой строке даны числа N, M (4≤N≤100, 1≤M≤100 ). Следующие N строк состоят из M символов каждая, и представляют собой саму картинку. Картинка устроена следующим образом:

• Первые K₁ строк в одной и той же позиции X₁ стоит символ «|», в остальных — пробел. Это веревка.
• Следующие K₂ строк в одних и тех же позициях с X₂ по X₃ стоит символ «#», в остальных — пробел. Это наковальня.
• 2×X₁=X₂+X₃, то есть наковальня подвешена за середину.
• Следующие K3 строк содержат только пробелы. Это пустота между наковальней и котом.
• Следующие N − K₁ − K₂ − K₃ строк содержат произвольные символы. Любой символ, кроме пробела — часть кота. Существует хотя бы один непробельный символ.

Числа K₁, K₂, K₃ и N − K₁ − K₂ − K₃  ненулевые.
Выходные данные
Выведите «YES», если при падении наковальня заденет Тома, в противном случае выведите «NO».
 

Примеры

№	Входные данные	Выходные данные
1	13 29 | | | ############# ############# ############# /\_/\ >^.^<.---. _'-`-' )\ (6--\ |--\ (`.`-. --' --' ``-'	YES
2	16 30 | ####### ####### ####### ####### , \)\_ / '. .---._ =P ^ ` '. `--. / \ .-'( \ | (.-' )-..__> , ; (_.--`` (__.-/ / .-.__.-'.' '-...-'	NO