Это более простая версия задачи H без запросов на изменение.
Лестер и Делберт работают в компании-производителе электроники. Сейчас они трудятся над микроплатой, которая должен соединять две независимые части большого суперкомпьютера.
Плата строится на основе макета в виде сетки. В макете \(n\) рядов и \(m\) столбцов, и на каждом пересечении ряда и столбца находится контакт. Также, на каждой из сторон макета расположены порты, которые можно подсоединять к ближайшему контакту. На левой и правой стороне находится по \(n\) портов, а на верхней и нижней — по \(m\) портов. Каждый из портов снаружи соединён с одной из частей суперкомпьютера, и раскрашен в красный либо синий цвет.
Порты можно соединять проводами внутри платы. Однако, есть несколько требований:
- Каждый провод должен соединять красный и синий порт, и каждый порт может быть соединён не более чем одним проводом.
- Каждый участок провода должен быть горизонтальным либо вертикальным, и повороты возможно только в одном из контактов.
- Чтобы избежать интерференции, провода не должны иметь общих частей ненулевой длины (однако, они могут проходить через общие контакты). Кроме того, провод не может покрывать один участок ненулевой длины дважды.
Пропускной способностью платы называется наибольшее количество соединений между красными и синими портами, которого можно достичь, соблюдая условия выше. Например, плата, изображенная выше, имеет пропускную способность \(7\), и один из способов построить семь соединений изображён ниже.
До этого места условия обеих версий задачи совпадают. Различия начинаются ниже.
Помогите Лестеру и Делберту найти пропускную способность платы с данной конфигурацией.