Дан связный неориентированный граф из \(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\)-м ребром. Гарантируется, что граф связный, в нем нет петель и кратных ребер.
Формат выходных данных
В единственной строке выходных данных выведите ответ на задачу.
Примечание
В первом тестовом примере одним из оптимальных способов получения ответа может быть изменение значения в вершине с номером \(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\).