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

Чтобы ничего не перепутать, мастера договорились, что Олег будет только включать лампы, а Сергей только выключать.

Театральная сцена представляет собой прямоугольник \(W\) на \(L\) метров, внутри которого расположено \(N\) ламп подсветки.

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

Перед началом спектакля Олег и Сергей получили подробный сценарий, в котором указано количество действий \(M\) и для каждого действия свой набор ламп подсветки, которые должны быть включены. Лампы, которые не входят в этот набор, должны быть выключены. Перед первым действием Олег должен находиться в левой части кулис, а Сергей - в правой. Изначально включены лампы, необходимые для первого действия.

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

В 2222 году экспедиция на планету XZ-238 в звездной системе ню Малой Медведицы обнаружила в одной из пещер загадочное устройство. Вдоль стены по прямой расположены \(n\) треугольных и \(n\) круглых гнезд. Расшифровка инструкций, расположенных рядом на стене, показала, что эти гнезда следует соединить проводами: каждое треугольное гнездо должно быть соединено с каким-либо круглым, расположенным правее.

Были изготовлены \(n\) треугольных и \(n\) круглых штекеров, которые можно соединять проводами. Однако никакой маркировки нет, поэтому понять какое гнездо следует соединить с каким не удается. Начальник экспедиции хочет заказать с Земли провода. Решено было заказать один большой моток кабеля, который затем нарезать на соединительные провода. Поскольку доставка грузов с Земли дорога, необходимо заказать как можно меньше кабеля. С другой стороны, поскольку неизвестно какое гнездо требуется соединить с каким, нужно заказать такое количество кабеля, чтобы при любом способе соединения длины кабеля хватило на изготовление соединительных проводов. Помогите руководству экспедиции по заданному расположению гнезд вычислить, кабель какой длины следует заказать. Гарантируется, что хотя бы один способ соединить гнезда описанным образом существует.

Например, рассмотрим расположение гнезд, изображенное на рисунке.

В случае же, показанном на следующем рисунке, есть лишь один способ соединить гнезда: \(1\) с \(A\), а \(2\) с \(B\). Гнездо \(2\) нельзя соединить с \(A\), поскольку \(A\) расположено левее. Так что в этом случае необходимо \(2\) метра кабеля.