Земля меду та молока

Погані чутки ширяться по Землі Меду та Молока. Знаючі люди кажуть, що молоко в знаменитих решітчастих молочних ріках стає кислим. Служба безпеки швидко виявила, що інформатори належать до королівства Тар, яке заздрить туристичній популярності землі. Однак це не зупинить чутки. Уряд прагне запобігти кризі в туристичній індустрії, тому планує запровадити щоденний моніторинг стану рік.

Створений Відділ Безпеки Молока має стежити за тим, щоб молоко в ріках не скисало. Він оснащений найпотужнішими бойлерами та пастеризаторами, тому будь-яка небезпека для молока має бути швидко нейтралізована. Для ефективної боротьби з новою загрозою відділу необхідно знати про можливі проблеми заздалегідь. У них є вертоліт, здатний перевіряти молоко на свіжість. Обладнання досконале: достатньо просто перетнути ріку в будь-якому місці, щоб виявити всі її потенційно небезпечні місця.

Щоб Відділ Безпеки Молока почав працювати, уряду потрібно виділити фінансування в бюджет Земельної Служби. Одним із завдань є побудова маршруту вертольота. Він повинен дослідити всі ріки за найкоротший час. Необхідно визначити вартість польоту і додати її в бюджет.

Решітка складається з двох типів молочних рік. Ріки першого типу течуть з Півночі на Південь, ріки другого типу — з Сходу на Захід. Усі ріки прямі. Ріки одного типу паралельні одна одній, відстані між сусідніми ріками відомі. Є $n$ рік, що течуть з Півночі на Південь, і $e$ рік з Сходу на Захід.

Уряд хоче підрахувати мінімальну вартість ранкового польоту. Кожен кілометр коштує $1$ барель меду, національної валюти Землі. Вартість зльоту та посадки не включається у вартість польоту. Початок і кінець польоту можна вибрати довільно.