В этой задаче вам предстоит составить недельное расписание пар в университете для преподавателей и групп студентов. Считайте, что учебных дней в неделе всегда 6, а максимальное количество пар в день равно 7 (пары в каждом дне пронумерованы от 1 до 7).

Известно, что в университете учится n групп студентов, работает m преподавателей и в нём есть a аудиторий, в которых можно проводить пары. Также вам задан двумерный массив размера n × m, содержащий следующую информацию. Число, записанное в i-й строке и j-м столбце равно количеству пар, которые преподаватель номер j должен провести у группы номер i за неделю. Составленное вами расписание должно удовлетворять описанному массиву.

Есть еще несколько условий для составления расписания. Один преподаватель не может одновременно вести более одной пары. Аналогично, студенты одной группы не могут одновременно присутствовать более чем на одной паре.

Введем определение функции усталости для преподавателей и групп студентов. Назовём эту функцию f.

Для одного преподавателя усталость подсчитывается следующим образом. Рассмотрим занятость преподавателя в каждый из 6-ти учебных дней. Пусть в день i текущий преподаватель первой для себя парой провёл пару номер x, а последней — пару номер y. Тогда к его усталости добавляется величина (2 + y - x + 1)·(2 + y - x + 1). Если в день i у текущего преподавателя не было пар, то к его усталости не добавляется ничего.

Для одной группы усталость подсчитывается аналогично. Рассмотрим пары, которые будут у текущей группы в каждый из 6-ти учебных дней. Пусть в день i у текущей группы первая для неё пара будет пара номер x, а последняя для неё пара — номер y. Тогда к усталости группы добавляется величина (2 + y - x + 1)·(2 + y - x + 1). Если в день i у текущей группы не было пар, то к её усталости не добавляется ничего.

Таким образом, значение функции f равно суммарной усталости для всех n групп и для всех m преподавателей.

Перед вами стоит задача составить такое расписание, которое минимизирует функцию f.

Жюри подготовило некоторое решение этой задачи. За каждый из тестов вы будете получать определенное количество баллов. Оно равно результату деления значения функции f, полученного решением жюри, на значение функции f, полученное из составленного вашей программой расписания (то есть чем меньше значение функции усталости получает ваше решение, тем больше баллов вы получите), умноженное на 100. Другими словами, если значение f в решении жюри равно p, а в вашем решении — q, то вы получите 100·p / q баллов (обратите внимание, что количество баллов является вещественным числом). Баллы за все тесты будут суммироваться. Ваша цель — набрать как можно больше баллов.