D. 玩绝区零玩的

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

你说得对,但是《绝区零》是由米哈游自主研发的一款全新动作类游戏。游戏发生在一个被称作「新艾利都」的奇妙都市,在这里,你将扮演名为「绳匠」的神秘角色,在自由的打工中邂逅性格各异、能力独特的同伴们,帮助他们探索空洞,挑战强敌——同时,逐步发掘「绳网」的真相。

新艾利都里一共有 个空洞,它们之间有 条双向道路连接着,每经过一条道路需要花费 的时间。

作为一名合格的绳匠,Shirost 在引导 uuku 探索空洞以前,需要对这 个空洞进行完全的勘测。空洞十分不稳定,每当进入第 个空洞时,将会遭遇第 个事件,其中:

  • 表示遭遇了战斗事件, uuku 的体力值下降
  • 表示遭遇了休息事件, uuku 的体力值上升

uuku 不希望这次探索之旅平平淡淡,他希望在包括起点和终点的探索过程中自己的体力值始终不低于 ,也不高于 ,即体力值 满足 。在进入空洞前 uuku 的体力值为

为了规划合理的路线, Shirost 需要知道对于所有 ,以第 个空洞为起点,第 个空洞为终点的所有合法路径耗时最小值。

由于 Shirost 分不清游戏和现实,请你帮他解决这个问题。

输入格式

输入第一行包含三个整数,分别代表空洞的数量 ,空洞间的道路数 ,以及体力值的阈值

第二行有 个整数,第 个整数 ​ 表示编号为 的空洞中遭遇的事件, 表示战斗事件, 表示休息事件。

到第 行,每行两个整数 ,代表从第 个空洞到第 个空洞有存在一条双向道路,通过该道路需要花费 的时间。

输出格式

输出共一行包含 个整数,第 个整数表示从 号点到第 个点至少需要花费多少时间,如果无解,请输出

样例

样例输入1

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

样例输出1

0 1 2 3 5 7 9 -1

数据范围与提示

数据范围

提示

进入 1 号空洞也会遇到相应事件。

可以重复进入空洞,每次进入时都将遭遇相应事件。