Константин и Михаил, два известных программиста на сайте Codeforces, после очередной олимпиады решили немного расслабиться. Они приобрели четыре ёмкости одинакового объёма, доверху наполненные алкогольными напитками — абсентом, бренди, сидром и джином. Абсент имеет крепость a, бренди имеет крепость b, сидр и джин имеют крепость c и d соответственно. Они хотели бы выпить по две ёмкости каждый таким образом, чтобы каждый из них принял бы одинаковую дозу алкоголя. Определите, могут ли они это сделать.
В первой строке записаны 4 целых числа a, b, c и d (0 ≤ a, b, c, d ≤ 100) — крепости всех четырёх напитков.
Если Константин и Михаил сумеют выполнить свой план, выведите YES, в противном случае выведите NO.
20 30 40 10
YES
0 20 40 95
NO
В рамках фестиваля интеллектуальных игр Муирамас проходит чемпионат по игре «Слабое звено». Игра состоит из нескольких раундов. В каждом из раундов команда получает вопрос от ведущего, обсуждает его в течение некоторого времени, после чего один из игроков должен сформулировать ответ от имени команды. Если ответ на вопрос неверный, игрок покидает команду и не принимает участия в раундах до конца игры.
Сейчас идёт очередной (и далеко не последний) раунд этой игры. Команда получила каверзный вопрос, и капитан команды предполагает, что придуманный ответ — неверный. Так что перед ним стоит трудная задача — решить, кому из команды поручить отвечать на этот вопрос.
Для каждого игрока команды известен его рейтинг, подсчитываемый по сложной формуле. Рейтинг команды определяется как сумма рейтингов игроков. Капитан понимает, что после ответа численность команды может уменьшиться на одного человека, и хочет выбрать отвечающего таким образом, чтобы в случае его ухода рейтинг команды остался максимально возможным.
Капитан обратился с этой задачей к Андрею Викторовичу, но Андрей Викторович был настолько занят проведением пар, что у него не хватило времени даже на подготовку этой задачи. Однако Андрей Викторович верит, что вы справитесь с этой задачей и поможете капитану.
В первой строке записано единственное целое число n (3 ≤ n ≤ 105) — количество игроков в текущем раунде.
Во второй строке записаны целые числа a1, a2, ..., an, где ai (0 ≤ ai ≤ 100) — рейтинг i-го игрока.
Выведите единственное целое число — максимально возможный рейтинг команды после этого раунда, если она даст неверный ответ.
4
3 5 2 0
10
6
10 1 1 1 1 1
14
Влад М. недавно окончил лицей и наконец-то поступил в лучший университет на свете — СГАУ! Влад — прирождённый лидер, поэтому одногруппники сразу же выбрали его своим старостой. Большая часть занятий в СГАУ проходит по подгруппам, и расписание составлено исходя из того, что каждая группа разделена на две подгруппы. Староста должен составить списки подгрупп и отнести их в деканат. Это означает, что Влад должен записать каждого студента в подгруппу #1 или в подгруппу #2. Разумеется, каждый студент должен быть записан ровно в одну подгруппу. Размеры подгрупп могут быть любыми; допустимо, что в одной из подгрупп может не быть ни одного студента.
Некоторые одногруппники уже успели сдружиться, а некоторые, напротив, уже недолюбливают друг друга. Так что на Влада посыпалась куча просьб вида «Я безумно влюблён в XX, поэтому хочу учиться с ней в одной подгруппе», «XY странно смотрит на меня, мне кажется, он сумасшедший, не хочу оказаться в одной подгруппе с ним» и т.д. Конечно, были и пожелания иного рода, например, «Я хочу учиться в подгруппе #1, так как там нет пар в 8 часов утра в понедельник». Но этих просьб и пожеланий было очень, очень много...
Предприняв несколько попыток составить списки подгрупп, Влад осознал, что это не так-то просто сделать. Поэтому он решил написать программу, выбирающую такое разбиение на подгруппы, при котором будет удовлетворено наибольшее количество просьб одногруппников.
«Достаточно просто перебрать все возможные разбиения на подгруппы и посчитать для каждого разбиения, сколько просьб будет выполнено. Плёвое дело!» — рассуждал Влад. Внезапно его посетила мысль, что количество возможных разбиений может быть настолько большим, что программа не сможет проверить их все не только до конца семестра, но и до конца обучения.
Зная, сколько человек учится в группе Влада, помогите ему определить количество возможных разбиений. Если возможных разбиений больше миллиона, скажите ему, что их слишком много. Два разбиения считаются различными, если найдётся хотя бы один студент, который в этих двух разбиениях записан в разные подгруппы.
В первой строке входных данных записано единственное целое число n (2 ≤ n ≤ 109) — количество студентов в группе Влада, включая его самого.
В первой строке выведите количество возможных разбиений на подгруппы.
Если количество возможных разбиений на подгруппы больше 106, выведите вместо количества возможных разбиений TOO HARD (в точности так, как записано).
3
8
21
TOO HARD
Пояснение к первому примеру.
Есть 8 способов разбиения:
1) первая подгруппа — студенты 1, 2 и 3, вторая подгруппа — никого;
2) первая подгруппа — студенты 1 и 2, вторая подгруппа — студент 3;
3) первая подгруппа — студенты 1 и 3, вторая подгруппа — студент 2;
4) первая подгруппа — студент 1, вторая подгруппа — студенты 2 и 3;
5) первая подгруппа — студенты 2 и 3, вторая подгруппа — студент 1;
6) первая подгруппа — студент 2, вторая подгруппа — студенты 1 и 3;
7) первая подгруппа — студент 3, вторая подгруппа — студенты 1 и 2;
8) первая подгруппа — никого, вторая подгруппа — студенты 1, 2 и 3.
Дано уравнение прямой ax + by + c = 0, причем a ≠ 0, b ≠ 0 и c ≠ 0. Требуется найти площадь треугольника, образованного этой прямой и координатными осями.
В первой строке записаны три целых числа a, b и c ( - 1000 ≤ a, b, c ≤ 1000, a ≠ 0, b ≠ 0, c ≠ 0) — коэффициенты в уравнении прямой.
Выведите вещественное число — площадь треугольника, образованного заданной прямой и координатными осями. Абсолютная или относительная погрешность результата не должна превышать 10 - 9.
2 -1 2
1.000000000000000
3 1 3
1.500000000000000
1 1 -2
2.000000000000000
Существует всего 7 типов тетрисных фигурок, «тетрамино»:
Дано клеточное поле размера n × m. Требуется замостить его тетрисными фигурками так, чтобы они не перекрывались и не осталось свободных клеток. Не обязательно использовать все типы фигурок.
В единственной строке записаны два целых числа n и m (1 ≤ n, m ≤ 50) — высота и ширина поля.
Выведите n строк, по m символов каждая. Каждый символ должен являться строчной латинской буквой. Каждая связная область, заполненная одной и той же буквой, должна описывать одну тетрисную фигурку. Соприкасающиеся по стороне тетрисные фигурки должны быть обозначены разными буквами.
Если решений несколько, выведите любое из них. Если же решения не существует, выведите единственное слово FAIL.
4 8
zzzffffb
zaaaxbbb
baeexxaa
bbbeexaa
7 7
FAIL
Представьте, что вы — квадратная шоколадка размера N × N. И у квадратных шоколадок проблем ничуть не меньше, чем у людей!
Сначала вам позвонили с неизвестного номера и попросили прийти в холодильник в 15:00 — там вам покажут, кто разбил яйца. Потом вам позвонила сахарница и сообщила, что если вы не придёте в 15:00 на кухонный стол, то между вами всё кончено. Чуть позже вам позвонили ваши чёрные братья — они попали в засаду, и им нужна ваша помощь в 15:00 около миксера...
В этот день вы получили k звонков. Каждый раз кому-то было жизненно необходимо ваше присутствие в определённом месте в 15:00; к тому же, все эти места оказались попарно различны. Вы очень приличная шоколадка, поэтому даже мысль о том, что вы опоздаете на какую-либо встречу или вообще пропустите её, для вас совершенно неприемлема.
К счастью, на каждом месте не обязаны присутствовать вы целиком; достаточно лишь вашей части — некоторой связной области из долек. За одно действие вы можете разломить ровно один цельный прямоугольный кусок себя (или вашей уже отломленной части) на два прямоугольных куска. Разламывать себя вы можете только по линиям, проходящим между дольками: по горизонтали или по вертикали.
Так же вы не хотите, чтобы кто-то из ваших друзей, позвонивших вам, посчитал себя обделённым. Поэтому вы должны разделить себя так, чтобы каждая часть состояла из одинакового количества долек, причём разделить себя вы должны полностью, т.е. не должно остаться неиспользуемых кусочков. Сможете ли вы оказаться в каждом месте и при этом не обидеть своих друзей?
Входные данные состоят из двух целых чисел N и k (1 ≤ N, k ≤ 1000) — размер вашей стороны в дольках и количество полученных просьб о встрече.
Выведите слово YES, если вы сможете побывать на всех встречах и не обидеть друзей, иначе выведите NO.
2 2
YES
3 4
NO
Каждое воскресенье Андрей вместе с друзьями играет в футбол. На каждую игру приходит одно и то же (чётное) количество человек. Когда друзья собираются, первым делом они начинают обсуждать, как им разделиться на две команды.
Обычно дискуссии по поводу того, как именно разделиться, занимают очень много времени. Однажды друзьям надоело дискутировать, и они придумали следующий способ. Каждый раз случайным образом выбираются два капитана, после чего капитаны набирают игроков в свои команды.
Чтобы не было новых споров и обид, капитаны по очереди выбирают по одному игроку среди тех, кто ещё не включён в какую-либо команду. Каждый капитан стремится набрать как можно более сильную команду и потому выбирает самого сильного среди ещё не выбранных игроков. Сила игрока — это целое число от 1 до 100 (как в FIFA). Сила команды вычисляется как суммарная сила всех игроков в этой команде, включая капитана.
Андрею стало интересно, какой может быть минимальная разница в силе между командами. Но он очень занят подготовкой контеста по программированию, поэтому просит вас найти эту величину.
На всякий случай ещё раз напомним, что в роли капитанов могут оказаться два любых игрока, не обязательно самые сильные.
В первой строке записано единственное целое число n (2 ≤ n ≤ 400) — количество человек, пришедших на игру. Гарантируется, что n — чётное.
Во второй строке записаны целые числа a1, a2, ..., an, где ai (1 ≤ ai ≤ 100) — сила i-го игрока.
Выведите единственное целое число — минимально возможную разницу в силе команд.
6
1 2 3 4 5 6
1
8
90 93 86 65 78 81 71 86
0
На прямой стоят n червей: i-ый червь находится в точке с координатой xi, причём никакие два червя не находятся в одной точке.
Маленький мальчик очень любит уничтожать червей. Для этого он использует оружие массового поражения «бетонный осёл». Каждое его применение создает копию бетонного осла шириной d, которая падает на прямую и уничтожает все живое на отрезке длины d. При этом края бетонного осла всегда будут находиться в точках с целыми координатами. Таким образом, каждая копия бетонного осла может уничтожить всех червей, которые расположены на некотором отрезке прямой [x, x + d].
Помогите маленькому мальчику определить, за какое наименьшее число применений бетонного осла он сможет уничтожить всех червей.
В первой строке записаны два целых числа n и d (1 ≤ n ≤ 105, 1 ≤ d ≤ 109) — количество червей, находящихся на прямой, и ширина бетонного осла.
Во второй строке записано n целых чисел x1, x2, ..., xn ( - 109 ≤ xi ≤ 109) — координаты точек на прямой, в которых расположены черви. Все координаты xi различны и упорядочены по возрастанию.
Выведите единственное целое число — минимальное количество применений бетонного осла, необходимое для уничтожения всех червей.
7 2
1 3 4 6 10 11 12
3
7 2
1 3 4 8 10 11 12
4
На прямой расположены n банков. Вор Жорж планирует ограбить их все, начиная с самого крупного (и продолжая их грабить в порядке уменьшения суммы денег в них). Известно, что i-ый банк расположен в точке с координатой xi, в нем хранится ai рублей, а чтобы его ограбить, Жоржу требуется ti минут. Перемещение на единицу расстояния занимает у Жоржа одну минуту. Все банки располагаются в разных точках прямой, и во всех банках хранится разное количество рублей.
Вы — полицейский, в последний момент узнавший о планирующейся операции. Единственное, что вы успеваете сделать — эвакуировать деньги ровно из одного банка. Эвакуированный банк, разумеется, будет проигнорирован Жоржем, как будто бы его и не существовало. Так как вы очень не любите Жоржа, вы решили эвакуировать такой банк, чтобы Жорж затратил как можно больше времени на ограбление всех остальных банков (полицейские начинают отсчет времени с начала первого ограбления). Может быть, вор устанет и проколется где-нибудь, а хоть какие-то деньги будут спасены. Если же таких банков несколько, то, так уж и быть, надо будет эвакуировать тот из них, в котором хранится больше всего денег.
Определите, какой банк следует эвакуировать.
В первой строке записано единственное целое число n (1 ≤ n ≤ 105) — количество банков.
В каждой из следующих n строк записано по три целых числа xi, ai и ti ( - 109 ≤ xi ≤ 109, 1 ≤ ai, ti ≤ 109) — координата i-го банка, количество денег в нём и время, требуемое на его ограбление. Все xi и ai различны.
Выведите номер банка, который следует эвакуировать. Так как суммы, хранящиеся в каждом из банков, различны, этот номер всегда определяется однозначно.
2
3 100 15
2 500 15
2
3
-2 700 1
2 900 8
4 1000 5
1
Это интерактивная задача. Ваша программа должна в процессе решения обмениваться информацией с программой жюри. Обратите внимание, что после вывода каждого сообщения ваша программа должна очищать потоковый буфер, чтобы выведенная вами информация дошла до программы жюри: например, это делают вызовы fflush(stdout) или cout.flush()в C++, System.out.flush() в Java, flush(output) в Pascal, Console.Out.Flush() в C#, sys.stdout.flush() в Python.
В 2020 году произошло невероятное событие — выпуск спин-оффа популярнейшей игры «Мафия» под названием «Комиссар против всех». В ней один игрок, являющийся комиссаром, пытается выявить K мафиози среди N жителей города 
.
Комиссар имеет возможность задать не более π·N вопросов высшему разуму (т.е. программе жюри). Каждый вопрос выглядит следующим образом. Комиссар выбирает любых K жителей города и спрашивает, есть ли среди них хотя бы один мафиози или нет.
Как только у комиссара будет достаточно информации, чтобы выявить всех мафиози, он завершает игру сообщением о том, кто из жителей города является членом мафии. Если это сообщение неверно или если комиссар попытается задать больше разрешённого количества вопросов, игра завершается победой мафии.
Миллионы желающих стремились стать первыми игроками в эту игру. Удачливее всех оказался Кирилл Комиссаров, студент Сицилийского университета. А на Сицилии, как известно, о мафии знают всё и все. Поэтому за игрой Кирилла будет наблюдать весь его университет. Да что там университет — его игру будет смотреть весь город, вся страна и даже весь мир!
Кирилл очень переживает, что не сможет придумать для заданных K и N правильную стратегию и проиграет мафии. Он просит вас помочь ему и написать программу, которая подскажет ему верные вопросы и абсолютно точно вычислит всех мафиози (за не более чем π·N вопросов).
В первой строке содержатся два целых числа N и K 
.
После каждого запроса вашей программы программа жюри выводит MAFIA, если среди перечисленных вами жителей города был хотя бы один мафиози, или FAIR, если среди них не оказалось ни одного мафиози.
Каждый запрос должен состоять из знака вопроса (?), после которого через пробел необходимо вывести ровно K различных целых чисел xi (1 ≤ i ≤ K, 1 ≤ xi ≤ N) — номера жителей города.
Сообщение о членах мафии должно начинаться с восклицательного знака (!), после которого через пробел должны быть выведены ровно K различных номеров жителей города, которых ваша программа определила как мафиози.
Ответ будет считаться верным, только если ваша программа правильно укажет номера всех K мафиози.
Выводить номера жителей в запросах и сообщении о членах мафии можно в любом порядке.
Напоминаем, что после каждого запроса и вывода сообщения о членах мафии следует очищать потоковый буфер.
5 2
ответ системы:
MAFIA
ответ системы:
MAFIA
ответ системы:
FAIR
ответ системы:
MAFIA
запрос участника:
? 1 2
запрос участника:
? 3 2
запрос участника:
? 3 4
запрос участника:
? 5 4
запрос участника:
! 2 5
Строки «запрос участника» и «ответ системы» в примере приведены лишь для того, чтобы было более понятно, в каком порядке выводятся сообщения. При решении задачи вам не нужно выводить эти строки, программа жюри также не будет выводить такие строки.
Как можно видеть, для пары (3, 4) программа жюри дала ответ FAIR, а для пар (2, 3) и (4, 5) был дан ответ MAFIA. Отсюда следует, что в этих парах именно жители 2 и 5 были мафиози. Поскольку мафиози всего 2, Кирилл заканчивает игру, указав пару (2, 5).
Лёша любит программирование и олимпиады и поэтому достаточно часто пишет раунды на сайте Codeforces. Однако за многие годы он так и не получил красный цвет. Тому есть целый ряд причин: иногда происходит перерасчёт рейтинга, иногда Лёша поздно приходит на работу и уже не успевает вернуться домой к раунду, а иногда он просто уклоняется от раундов китайских авторов, поскольку считает, что они плохого качества.
Но сегодня не такой день, сегодня всё складывается очень хорошо: раунд не китайский, Лёша пришёл на работу вовремя, и, главное, он каким-то образом узнал темы задач и разбалловку!
В раунде будет n задач. Изначально i-я задача оценивается в ai баллов, однако каждую минуту её стоимость уменьшается на bi баллов. Таким образом, если i-я задача была решена на минуте mi от начала соревнований, участнику будет начислено за нее costi = ai - bi·mi баллов. Леша решает все задачи подряд, и не тратит время на отдых. Он уверен, что независимо от того, какой порядок он выберет, на момент решения i-й задачи ее стоимость будет положительна.
Также для каждой задачи Лёша знает время ti, в течение которого он напишет её решение: время решения задачи Лёшей зависит исключительно от того, на какую тему эта задача, а темы, как мы помним, он выяснил.
Конечно, Лёша хочет набрать максимально возможное количество баллов. Он догадывается, что количество набранных баллов зависит от порядка решения задач. Но сейчас он на работе и не хочет опоздать на раунд, так что вопрос определения порядка задач, обеспечивающего максимально возможное количество баллов, перекладывается на вас.
В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество задач в раунде.
В каждой из следующих n строк содержится по три целых числа ai, bi, ti (1 ≤ ai ≤ 1014, 1 ≤ bi, ti ≤ 103) — описание очередной задачи.
В первой строке выведите n чисел — номера задач в том порядке, который обеспечивает максимально возможное количество баллов.
Если существует несколько ответов, выведите любой.
5
500 2 10
1000 4 12
1500 6 37
2000 8 42
2500 10 23
5 2 1 4 3
Таня уже 4 года занимается олимпиадным программированием. Увы, в этом году её команда не прошла в полуфинальный этап соревнований, и поэтому Таня присутствует на нём в качестве зрителя и болеет за команду Андрея.
В основном зрителями являются тренеры и руководители команд. Многие тренеры проводят в своих вузах разные соревнования, и у них есть традиция — на полуфинале обмениваться друг с другом книжечками, посвящёнными этим соревнованиям. Тренер Тани не может присутствовать на полуфинале, и теперь у Тани есть бесконечное количество книжечек, которые её попросили передать другим тренерам. Конечно, нужно сказать, что Таня не смогла отказать тренеру в просьбе передать книжечки, что она очень хотела перепоручить это важное дело Андрею, и что Андрей (смог откосить) убедил Таню в том, что никого из тренеров он не сможет увидеть: ведь для тренеров и других зрителей организуются разные мероприятия, пока участники соревнований пишут контест.
На полуфинале запланировано n мероприятий для тренеров и других зрителей. Эти мероприятия пронумерованы от 1 до n в порядке времени проведения, при этом ни одно мероприятие не пересекается с каким-либо другим. На i-м мероприятии Таня может успеть раздать ai книжечек. Проблема в том, что Таня социофоб, и общение с тренерами (а тренеры не могут просто взять книжечку, а непременно хотят поговорить) для неё очень утомительное и тяжёлое дело. Поэтому, если Таня посетила некоторое мероприятие, после него она убегает в свой номер в гостинице и находится там как минимум в течение следующих k мероприятий. Ваша задача — определить максимальное количество книжечек, которое Таня сможет раздать.
На всякий случай уточним, что ни одно мероприятие не проходит у Тани в номере, так что пока она там находится, раздавать книжечки она не может.
В первой строке записаны целые числа n и k (1 ≤ n, k ≤ 2·105) — количество мероприятий для тренеров и зрителей и количество мероприятий, которые Таня пропускает, пока находится в своём номере, соответственно.
Во второй строке записаны n целых чисел a1, a2, ..., an, где ai (1 ≤ ai ≤ 109) — количество книжечек, которые Таня может раздать на i-м мероприятии.
Выведите единственное целое число — максимальное количество книжечек, которое сможет раздать Таня.
5 1
1 4 6 5 1
9
3 2
1 2 3
3
Пояснение к первому примеру.
Тане следует пойти на 2-е мероприятие, раздать там 4 книжечки, затем в течение 3-го мероприятия отдыхать в номере, а потом пойти на 4-е мероприятие и раздать там ещё 5 книжечек.
Назовём скобочную последовательность идеальной, если она образована некоторым количеством открывающих скобок, за которыми следует такое же количество закрывающих скобок. Глубиной идеальной скобочной последовательности назовём количество скобок какого-то одного вида в ней. Глубиной скобки назовём количество скобок того же вида, включая её саму, до ближайшего к ней края последовательности. Например, последовательность (((()))) имеет глубину 4, а скобки в ней имеют глубины 1, 2, 3, 4, 4, 3, 2 и 1 соответственно.
Очевидно, что любую скобочную последовательность можно преобразовать в идеальную (возможно, пустую), если удалить из неё некоторое количество скобок.
Вам дана скобочная последовательность, возможно, неидеальная. Для каждой скобки в этой последовательности требуется определить две величины:
- максимально возможную глубину данной скобки в идеальной скобочной последовательности, полученной удалением некоторых скобок из исходной последовательности;
- максимально возможную глубину идеальной скобочной последовательности, в которую входит эта скобка; идеальная скобочная последовательность получается удалением некоторых скобок из исходной последовательности.
Если какая-то скобка не входит ни в какую идеальную скобочную последовательность, которую можно было бы получить удалением некоторых скобок из исходной последовательности, обе величины будем считать равными 0.
В единственной строке записана скобочная последовательность s, состоящая только из открывающих и закрывающих скобок. Ее длина length(s) находится в пределах от 1 до 105.
В первой строке выведите length(s) чисел — ответы на первый вопрос задачи для каждой скобки.
Во второй строке выведите length(s) чисел — ответы на второй вопрос задачи для каждой скобки.
(()())
1 2 2 2 2 1
2 2 2 2 2 2
))()(()(())())()((
0 0 1 1 2 3 3 4 5 5 4 3 3 2 1 1 0 0
0 0 5 1 5 5 3 5 5 5 5 3 5 5 1 5 0 0
Андрей Викторович уже третий год проводит тренировки в олимпиадном кружке СГАУ. В этом году он узнал, что, как опытный тренер, он может претендовать на грант университета Силопонни. Для этого ему надо провести n тренировок, в каждой из которых должно принять участие не менее m студентов. Кроме того, всего в тренировках должны поучаствовать не менее k различных студентов.
Также Андрей Викторович читает лекции в университете, на которые ходят a студентов. В конце семестра Андрей Викторович ставит экзамен автоматом тем студентам, которые набрали достаточное количество бонусных баллов. Одним из способов получения бонусных баллов является участие в тренировках.
Впрочем, студенты полагают, что участие в тренировках нужно не только им, но и Андрею Викторовичу, поэтому j-й студент согласен прийти не более чем на cj тренировок, причём только в том случае, если получит за каждую из них по dj бонусных баллов. Некоторые студенты являются поклонниками Андрея Викторовича (они даже организовали «Gaidel Fan Club»), поэтому они готовы приходить на тренировки, не получая бонусных баллов.
Андрей Викторович волен выбирать, каких именно студентов и на какую тренировку он позовёт. Студенты, которых Андрей Викторович не позвал, на тренировку не придут и бонусных баллов не получат.
Конечно, Андрей Викторович хочет получить грант. Но поскольку он считает, что всех студентов следовало бы отчислить, он хочет выдать минимально возможное количество бонусных баллов. Помогите ему определить это количество. Если выполнить все условия гранта нельзя, выведите сообщение о том, что Андрей Викторович плохой тренер.
В первой строке содержатся три целых числа n, m, k (1 ≤ n ≤ 105, 1 ≤ m ≤ k ≤ 105) — количество тренировок, минимальное количество студентов на одной тренировке и минимальное количество студентов, которые должны принять участие хотя бы в одной тренировке.
Во второй строке содержатся единственное целое число a (1 ≤ a ≤ 105) — количество студентов, у которых читает лекции Андрей Викторович.
В каждой из следующих a строк содержится по два целых числа ci и di (1 ≤ ci ≤ 105, 0 ≤ di ≤ 106) — максимальное количество тренировок, которое согласен посетить i-й студент, и количество бонусных баллов, которое он хочет получить за каждую тренировку.
В первой строке выведите единственное целое число — минимальное количество бонусных баллов, которые придётся выдать Андрею Викторовичу, чтобы получить грант.
Если же Андрею Викторовичу не удастся получить грант, выведите вместо числа Bad Coach (в точности, как написано).
4 3 5
5
4 0
4 0
4 0
3 1
3 2
3
4 3 6
5
4 0
4 0
4 0
3 1
3 2
Bad Coach