时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小H购买了一辆新能源汽车，想用它来周游全国。

　　为节能减排，政府在这个国家的交通网络中设置了 \(N\) 个新能源车充电站（编号为 \(1..N\)），这 \(N\) 个充电站的位置都是经过科学论证，即从任意一个充电站到相邻的充电站之间有一条公路，这些公路的行驶时间都为T（分钟）。由于技术限制，新能源车要求每经过三个充电站就必须停下来为其充电（也可以说每经过三条公路就必须停下来充电），但每个充电站给汽车充满电的时间不一定相同，即第 \(i\) 个充电站充满一辆汽车电的时间为 \(W_i\)（分钟）。

　　小H的家在 1 号充电站所在的位置。有一天他打算自驾新能源汽车到 \(N\) 号充电站的城市去旅游，请你帮小H计算一下，他在旅途中最少要花多少时间？注意小H在 1 号站出发时，就会把汽车的电充满，但这个充电时间不计入旅途的时间。

【输入格式】

　　第一行包含两个整数：\(N,M\) 和 \(T\)，\(N\) 表示电站的数目，\(M\) 表示充电站之间的公路数目，\(T\) 表示每条公路的行驶时间（分钟）。
　　接下来的一行，包含 \(N\) 个整数，其中第 \(i\) 个整数为 \(W_i\)，表示第 \(i\) 个充电站为汽车充满电的时间是 \(W_i\) 分钟。
　　再接下来的 \(M\) 行，每行包含两个整数 \(u,v\)，表示充电站 \(u\) 和 \(v\) 之间有一条公路。

【输出格式】

　　一行一个整数，表示旅途的最短时间。

【输入输出样例】

　Input

7 9 2
20 15 18 5 21 8 10
1 2
1 3
2 3
2 4
3 4
3 5
4 5
5 6
6 7

　Output

16

【样例解释】

　　旅途路线：1-3-5-6-7，花费时间为2+2+2+2=8分钟，其中在6号站充电8分钟，总时间为为8+8=16分钟。

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤10000\)，\(1≤M≤20000\)，\(1≤w_i,T≤1000000\)。

【来源】

　　Mr.he