Майора Рама преследует его заклятый враг Рагхав. Рам должен добраться до вершины здания, чтобы сбежать на вертолете, однако здание горит. Рам должен выбрать оптимальный путь, чтобы добраться до вершины здания, потеряв минимальное количество здоровья.
Здание состоит из \(n\) этажей, на каждом этаже \(m\) комнат. За \((i, j)\) обозначим \(j\)-ю комнату на \(i\)-м этаже. В здании \(k\) лестниц. \(i\)-я лестница позволяет Раму подняться из комнаты \((a_i, b_i)\) в \((c_i, d_i)\), но не в другом направлении. За проход по \(i\)-й лестнице Рам получает \(h_i\) очков здоровья. Гарантируется, что для всех лестниц \(a_i < c_i\).
Если Рам находится на \(i\)-м этаже, то он может двигаться влево или вправо. Путешествовать по этажам, однако, сложно, поэтому если Рам переходит от комнаты \((i, j)\) к \((i, k)\), он теряет \(|j-k| \cdot x_i\) очков здоровья.
Изначально Рам находится в комнате \((1, 1)\), а вертолет ожидает его в \((n, m)\). Какое минимальное количество очков здоровья Рам может потерять, если выберет оптимальный путь? Обратите внимание, что этот ответ может быть отрицательным (в этом случае он наберет очки здоровья). Выведите «NO ESCAPE», если Рам никак не может добраться к вертолету.
Выходные данные
Выведите минимальное число очков здоровья, которое Рам может потерять на пути от \((1, 1)\) до \((n, m)\). Если Рам не может добраться до вертолета, выведите «NO ESCAPE» (заглавными буквами без кавычек).
Примечание
Рисунок в условии демонстрирует первый пример из условия. Есть только \(2\) возможных пути к \((n, m)\):
- Рам идет в \((1, 3)\), поднимается по лестнице в \((3, 3)\), идет в \((3, 2)\), поднимается по лестнице в \((5, 1)\), идет до \((5, 3)\), откуда улетает на вертолете. Потери здоровья равны \(\) \begin{align*} &\mathrel{\phantom{=}} x_1 \cdot |1-3| - h_1 + x_3 \cdot |3-2| - h_3 + x_5 \cdot |1-3| \\ &= 5 \cdot 2 - 4 + 8 \cdot 1 - 6 + 4 \cdot 2 \\ &= 16. \end{align*} \(\)
- Рам идет в \((1, 3)\), поднимается по лестнице в \((3, 3)\), идет в \((3, 1)\), поднимается по лестнице в \((5, 2)\), идет до \((5, 3)\) , откуда улетает на вертолете. Потери здоровья равны \(\) \begin{align*} &\mathrel{\phantom{=}} x_1 \cdot |1-3| - h_1 + x_3 \cdot |3-1| - h_2 + a_5 \cdot |2-3| \\ &= 5 \cdot 2 - 4 + 8 \cdot 2 - 5 + 4 \cdot 1 \\ &= 21. \end{align*} \(\)
Минимальная потеря здоровья равна
\(16\).
Во втором примере нет пути в \((n, m)\).
В третьем примере Рам идет в \((1, 3)\), а затем поднимается по лестнице в \((5, 3)\). Он теряет \(5 \cdot 2\) очка здоровья и затем получает \(h_1 = 100\) очков. Поэтому его потери равны \(10-100=-90\) (отрицательное число означает, что он улучшил здоровье).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 3 3
5 17 8 1 4
1 3 3 3 4
3 1 5 2 5
3 2 5 1 6
6 3 3
5 17 8 1 4 2
1 3 3 3 4
3 1 5 2 5
3 2 5 1 6
5 3 1
5 17 8 1 4
1 3 5 3 100
5 5 5
3 2 3 7 5
3 5 4 2 1
2 2 5 4 5
4 4 5 2 3
1 2 4 2 2
3 3 5 2 4
|
16
NO ESCAPE
-90
27
|