Мария Петровна работает преподавателем в университете.

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

Мария Петровна знает, что каждый из ее студентов относится к одной из трех категорий:

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

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

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

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

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

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

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

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

Будем считать, что в узлы решетки размером \(n\times m\) высажены деревья. Два дерева считаются соседними, если узлы, в которых они растут, являются соседними по вертикали или по горизонтали. У каждого дерева есть своя высота, равная некоторому целому числу метров.

Павел считает, что высота деревьев изменяется с годами по следующему закону:

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

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

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

Чтобы стать джедаем, необходимо овладеть многими теоретическими и практическим навыками. В Академии Джедаев можно обучиться всему необходимому, если, конечно, у тебя есть способности.

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

Академия состоит из двух корпусов, в одном из которых обучают теоретическим навыкам, а в другом - практическим. Путь из одного корпуса в другой занимает ровно \(a\) минут. Изучение любого навыка занимает ровно \(b\) минут. В начальный момент Фил находится в общежитии, путь от которого до каждого из корпусов также занимает \(a\) минут.

Разумеется, навыки нельзя изучать в произвольном порядке. Например, прежде чем овладеть световым мечом, нужно сначала изучить основы оптики и искусство рукопашного боя. Филу важно учесть это при составлении своего расписания.

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

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

Поле для выполнения задания представляет собой прямоугольник размером \(n \times m\) метров, разбитый на квадраты единичной площади. В одном из квадратов исходно находится Артур, в некотором другом квадрате находится котенок. Кроме того, один из квадратов содержит лифт, встав на который вместе с котенком, Артур успешно выполняет задание.

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

Выяснив, сколько шагов ему придется сделать, Артур заинтересовался, сколько существует различных способов дойти до котенка, а затем с ним до лифта, сделав в сумме минимальное число шагов. Помогите ему это выяснить. Это число может быть довольно большим, поэтому Артур просит найти его по модулю \(10^9+7\).

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

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

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

За нарушение закона был введен штраф в размере \(a\) рублей.

Узнав о законе, Петя решил выяснить, какой штраф может быть наложен на жильцов его дома. Дом, в котором живет Петя, имеет \(n\) этажей, на каждом этаже находится по \(m\) квартир. Квартиры в доме пронумерованы от 1 до \(nm\). Если на некотором не последнем этаже находится квартира номер \(x\), то непосредственно над ней расположена квартира номер \(x + m\).

Известно, что в \(i\)-й квартире живет \(b_i\) котов. Петя предположил, что жильцы некоторой квартиры будут жаловаться на соседей сверху только в том случае, если коты сверху топают существенно громче, чем их собственные. Проведя эксперименты, Петя решил, что \(p\) котов топают существенно громче, чем \(q\) котов, если \(p > 2q\).

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