Дан связный неориентированный граф из $$$n$$$ вершин. Изначально в $$$i$$$-й вершине ($$$1 \leq i \leq n$$$) записано целое положительное число $$$a_i$$$. Боб хочет за минимальное время попасть из вершины с номером $$$1$$$ в вершину с номером $$$n$$$. Время, которое требуется, чтобы пройти по ребру, соединяющему вершины $$$u$$$ и $$$v$$$, составляет $$$|a_u - a_v|$$$.
Перед тем, как начать обход, Боб может поменять значение $$$a_i$$$ в не более чем $$$k$$$ вершинах. За какое минимальное время можно попасть из $$$1$$$ в $$$n$$$, поменяв значения оптимальным образом?
В первой строке входных данных записаны три целых числа $$$n, m, k$$$ ($$$2 \leq n \leq 2000, 1 \leq m \leq 2000, 0 \leq k \leq 10$$$) — количество вершин графа, количество ребер и параметр $$$k$$$ соответственно.
В следующей строке содержится $$$n$$$ целых чисел $$$a_i$$$ ($$$0 \leq a_i \leq 10^9$$$) — начальные значения в вершинах.
В следующих $$$m$$$ строках содержатся пары чисел $$$u_i, v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) — вершины, соединенные $$$i$$$-м ребром. Гарантируется, что граф связный, в нем нет петель и кратных ребер.
В единственной строке выходных данных выведите ответ на задачу.
Решения, верно работающие в случае, когда все $$$a_i \leq 20$$$, будут получать не менее 35 баллов.
Решения, верно работающие в случае, когда $$$m = n - 1$$$ и существует ребро между вершинами $$$i$$$ и $$$i + 1$$$ ($$$1 \leq i \leq n - 1$$$), будут получать не менее 29 баллов.
Решения, верно работающие в случае, когда граф не содержит циклов, будут получать не менее 47 баллов.
Решения, верно работающие в случае, когда $$$k=0$$$, будут получать не менее 29 баллов.
Решения, верно работающие в случае, когда $$$n \leq 300$$$, будут получать не менее 60 баллов.
6 7 11 15 5 10 4 101 22 33 61 44 55 62 5
9
6 7 31 15 5 10 4 101 22 33 61 44 55 62 5
0
В первом тестовом примере одним из оптимальных способов получения ответа может быть изменение значения в вершине с номером $$$2$$$ с числа $$$15$$$ на число $$$3$$$. В таком случае путь $$$1 \rightarrow 2 \rightarrow 5 \rightarrow 6$$$ будет иметь стоимость $$$|1 - 3| + |3 - 4| + |4 - 10| = 9$$$.
Второй пример отличается от первого лишь значением $$$k$$$. Во втором примере можно поменять значения записанные в вершинах с номерами $$$2, 3, 6$$$ на $$$1$$$. Тогда стоимостью пути станет $$$|1 - 1| + |1 - 1| + |1 - 1| + |1 - 1| = 0$$$.