题目背景

零夜7号-白鹰

题目描述

白鹰是天空的王者，它在连绵的山脉中翱翔。山脉中有 \(n\) 座山峰，编号从 \(1\) 到 \(n\)，第 \(i\) 座山峰的高度为 \(h_i\)。山峰之间有 \(m\) 条双向的飞行路径，连接山峰 \(u\) 和山峰 \(v\)。白鹰从山峰 \(1\) 出发，要飞到山峰 \(n\)。

白鹰每次沿着一条路径从山峰 \(u\) 飞到山峰 \(v\) 时，会消耗 \(|h_u - h_v|\) 点体力。但是，白鹰有一个特殊的能力：它可以在飞行过程中使用最多 \(k\) 次"滑翔"技能。当白鹰使用滑翔技能飞行时，消耗的体力会变成 \(\lfloor|h_u - h_v| / 2\rfloor\)（向下取整）。

白鹰想知道，它从山峰 \(1\) 飞到山峰 \(n\) 的最小体力消耗是多少？

输入格式

第一行三个整数 \(n, m, k\)，分别表示山峰的数量、飞行路径的数量和白鹰最多可以使用的滑翔技能次数。

第二行 \(n\) 个整数 \(h_1, h_2, \dots, h_n\)，表示每座山峰的高度。

接下来 \(m\) 行，每行两个整数 \(u, v\)，表示一条双向的飞行路径连接山峰 \(u\) 和山峰 \(v\)。

输出格式

输出一个整数，表示白鹰从山峰 \(1\) 飞到山峰 \(n\) 的最小体力消耗。如果无法到达，输出 -1。

输入输出样例 #1

输入 #1

5 6 1
1 7 3 2 5
1 2
1 3
2 4
3 4
3 5
4 5

输出 #1

3

输入输出样例 #2

输入 #2

3 2 0
1 10 100
1 2
2 3

输出 #2

99

说明/提示

样例 1 解释

最优路径是 \(1 \to 3 \to 5\)：
- \(1 \to 3\) 使用普通飞行，消耗 \(|1-3|=2\) 点体力
- \(3 \to 5\) 使用滑翔技能，消耗 \(\lfloor|3-5|/2\rfloor=1\) 点体力
- 总消耗 \(2+1=3\) 点体力

数据范围

• 对于 \(30\%\) 的数据，\(k=0\)
• 对于 \(60\%\) 的数据，\(1 \le n \le 1000\)，\(1 \le m \le 2000\)，\(k \le 10\)
• 对于 \(100\%\) 的数据，\(1 \le n \le 10^4\)，\(1 \le m \le 2 \times 10^4\)，\(0 \le k \le 20\)，\(0 \le h_i \le 10^9\)