С целью упрощения ЕГЭ по литературе, было решено оставить в нем вопросы только с ответами «да» или «нет». Бланк ответов представляет клетчатое поле из \(N\) строк и \(M\) столбцов, в котором каждая клеточка соответствует своему вопросу. Ученику необходимо один раз перечеркнуть по диагонали те клеточки, которые, по его мнению, соответствуют вопросам с ответом «нет» (перечеркивать можно по любой из двух диагоналей). При этом во избежание ошибок при сканировании, никакие две диагонали не должны "сливаться", то есть иметь общий конец.

Авторам варианта необходимо знать, какое наибольшее количество вопросов с ответом «нет» можно вставить в вариант, чтобы бланк с правильными ответами мог быть верно распознан компьютером.

Один из столичных девелоперов решил построить жилой дом по проекту известного авангардного архитектора. Жилой дом будет состоять из квартир-кубиков и иметь причудливую форму. Есть два ограничения, одно из которых наложено архитектором, а второе — законами физики.

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

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

В приведенном примере показаны привлекательности видов из окна и наилучшее здание из 10 кубиков в данном случае.

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

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

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

Завтра Петя уезжает в кругосветное путешествие, в процессе которого собирается посетить N разных городов. Вспомнив о старинной традиции бросать монетки в фонтаны для того, чтобы когда-нибудь вернуться в это место, он решил запастись монетами заранее. Поскольку это всего лишь традиция, подумал Петя, то с него хватит оставить в каждом городе по одной копеечной монете – зачем тратиться зря?

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

С этими мыслями Петя решил прогуляться до продуктового магазина – купить в дорогу немного еды. Из всего ассортимента ему подходило M видов товара (количество товаров каждого вида неограниченно), стоимость i-го равна a_i рублей b_i копеек. И тут его осенило. Если покупать товары в правильной последовательности, то он довольно быстро сможет скопить так нужные ему N копеечных монет!

Процесс покупки в магазине устроен следующим образом. Петя может заказать любой набор из подходящих ему товаров (каждого товара Петя может взять сколько угодно единиц). После чего он платит за них и получает сдачу минимальным числом купюр и монет (любых монет и купюр в кассе также с избытком). Это означает, например, что если ему должны сдать 11 рублей и 98 копеек сдачи, то он получит купюру в 10 рублей, монеты в 1 рубль, 50 копеек, 4 монеты в 10 копеек, одну монету в 5 копеек и три копеечных монеты. При этом он волен вносить любую сумму (лишь бы она была не меньше требуемой для оплаты) и платить любым набором купюр и монет, имеющихся у него в распоряжении.

После этого Петя может ещё раз подойти к кассе, сделать заказ, расплатиться имеющимися наличными (можно использовать и полученные до этого со сдачей) и так далее сколько угодно раз.

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

Комментарий для нероссийских участников олимпиады.

В России используются монеты и купюры достоинством 1, 5, 10, 50 копеек и 1, 2, 5, 10, 50, 100, 500, 1000 и 5000 рублей. 1 рубль равен 100 копейкам.