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

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

На ферме есть N × M птиц. Джонни соорудил каждому страусу по загону, установив перегородки так, чтобы они образовывали прямоугольник из N строк и M столбцов. Тем самым образуется ровно N × M квадратных загонов 1 × 1. Обратите внимание: между соседними загонами он ставил ровно одну перегородку, а не две.

В один прекрасный осенний день заслуженный страус Чак, находившийся в нижнем левом загоне, почувствовал острую необходимость отправиться по важным и неотложным страусиным делам. Он начал пробивать себе путь на волю, ломая перегородки. Сначала он сломал правую перегородку и переместился загоном правее. Потом он сломал верхнюю перегородку и переместился вверх. Далее он прокладывал себе путь по такому же принципу: ломая попеременно то правую, то верхнюю перегородку, пока, наконец, не оказался на свободе.

Джонни, увидев разгром, учиненный Чаком, сильно расстроился. Но делать нечего — надо приводить все в порядок. Он отправил письмо на ближайшую лесопилку, указав, сколько у него осталось перегородок, но забыв при этом указать, сколько ему требуется.

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

Иннокентий устроил ремонт на кухне. Как профессиональный строитель, он прекрасно знает, что для кухни нет ничего лучше кафельной плитки.

Кухня Иннокентия представляет собой прямоугольник W на H метров. К сожалению, нужная плитка продается только в одном магазине. Каждая плитка имеет фиксированный размер a на b метров, и на нее нанесен интересный узор. Для того, чтобы пол кухни выглядел красиво, плитку надо класть так, чтобы каждая сторона плитки граничила максимум с одной плиткой и была параллельна одной из сторон кухни. Узор является очень специфическим, поэтому плитки нельзя поворачивать, даже все одновременно — сторона кухни длиной W должна быть всегда параллельна стороне плитки длиной a.

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

Помогите Иннокентию выяснить, какое минимальное число целых плиток размером a на b нужно купить, чтобы красиво замостить всю кухню.

Создатели мультсериала «Футурама» при разработке серий используют нумерацию, которая называется «код серии». Все серии разбиты на производственные блоки. Код серии имеет вид: xACVyy, где x — номер производственного блока (возможно, двузначный), а yy — номер серии в блоке (обязательно двузначный, возможно, с ведущим нулем). При показе по телевизору используется другая нумерация, называемая «код показа». Код показа имеет вид SxxEyy, где xx — номер сезона, а yy — номер серии в сезоне. Числа xx и yy обязательно двузначные, возможно, с ведущим нулем. Порядок и суммарное количество серий при создании и показе совпадает.

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

В супермаркете «На троечку» часто происходят распродажи товаров, срок годности которых подходит к концу. Каждый товар привозят в магазин в определенное время, а через некоторое его вывозят из магазина, в связи с окончанием срока годности. Более формально, каждый товар имеет стоимость c_i, время его завоза в магазин a_i и время его вывоза из магазина b_i.

У Иннокентия есть хитрый план похода в магазин. Даже несколько. Каждый план похода в магазин выглядит так: Иннокентий выбирает какое-то время, когда он появится в магазине m_j, время s_j, которое он проведет в магазине среди огромных стеллажей товаров, и сумму денег k_j, которую он рассчитывает потратить. Для каждого плана он хочет узнать, сможет ли он осуществить его, т. е. верно ли, что он сможет во время своего пребывания в магазине купить несколько товаров суммарной стоимостью ровно k_j, при этом все выбранные товары должны быть в магазине на протяжении всего пребывания Иннокентия в магазине.

Помогите Иннокентию определить, какие из его планов можно выполнить.