— Все-таки мне кажется неосмотрительным показывать такую документацию совершенно постороннему человеку, — Крис вернул стопку Элис и уже вознамерился завершить разговор и откланяться.

— Ну уж не такой и посторонний! — чуть рокочущий голос раздался из-за спины Криса. Крис обернулся. Да, это был Саймон. Их дороги с Крисом пересекались уже несколько раз. Саймон считал себя великим программистом и еще более великим руководителем. Его ничуть не смущало, что до сих пор все его проекты и фирмы лопались, как мыльные пузыри. В чем, впрочем, никак ему нельзя было отказать — так это в умении столь красочно рассказывать о светлом будущем очередной своей задумки, что многие из тех, кто имел возможность уже не один раз наблюдать бесславное окончание предыдущих планов, начинали верить, что уж на этот раз у Саймона все получится.

— На самом деле мы временно ютимся в этом здании, сейчас для нас проектируют новый офис в поселке «Синий Тракторист». Окна прямо в лес будут выходить! Там, правда, еще придется немного повозиться, чтобы построить нормальную дорогу для спецтехники, а то понастроили заборов. Но у меня уже есть нужные бумаги, так что заборовладельцам придется подвинуться! — Саймону явно не терпелось продемонстрировать свою значительность.

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

Карта поселка представляет собой прямоугольник размера N × M. Будем считать, что он разбит на квадраты с единичной стороной. Частные землевладения также представляют собой прямоугольники, стороны которых параллельны сторонам карты, при этом для каждого квадрата с единичной стороной верно, что он либо полностью принадлежит некоторому землевладению, либо полностью не принадлежит никакому землевладению. Никакие два землевладения не перекрываются. Квадраты с координатами (1, 1) (левый верхний угол) и (N, M) (правый нижний угол) не заняты никакими землевладениями. Дорога должна соединить эти квадраты.

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

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