U405212 幽雅に咲かせ、墨染の桜

  这天，深冬， yhy 过度沉迷于切黑题，导致她去拿外卖的时候迟到了 $1$ 分钟，自然，外卖被偷了。寒风中， yhy 站在路边，这场外卖被偷的变故像一盆冷水，浇灭了她击破 $100$ 道黑题的兴奋，美好的外卖是对一天的劳累的慰藉，可如今却烟消云散，想必……这便是期望落空的感觉吧……   微风飘动，一片片粉色的樱花拂过 yhy 的脸颊……   ——可是现在并不是樱花开放的时节   她抬起头，映入眼帘的是一个熟悉却又理应不该存在的身影——西行寺幽幽子。   yhy睁大了眼睛，眼神里充满着不可思议，此刻，无论是刚刚AC 100道黑题的兴奋还是外卖被偷的失落，全都被这个来自于幻想乡的身影所带来的惊讶冲散了。   “你好呢，现世的朋友。”   “不要惊讶，穿过结界什么的，紫有在帮忙哦，我只是来这里赏樱啦……”   “这里没有樱花……怎么会呢，我不是说了 ‘ 我只是来这里赏樱 ’ 了嘛。樱花很快会绽放的。”   “欸……有在枯萎呢……或许，只有寒风的话，可不利于樱花绽放呢……你的失落，是有什么心事嘛？”   “欸……外卖？食物嘛？消失的话，的确令人失落呢……那，你可以陪我一起赏樱嘛？嘛，果然这样的提议还是有些太突然了，其他的意图？不知道呢，只是有人同行的话，景致或许会更为生动一些吧。年年绽放的樱花，景色或许相同，千年依旧，改变的或许只有同行的人吧？紫、妖梦……还有你，我会让妖梦为你多准备一份料理的，好嘛？”

**与题意有关的句子已加粗。**   “ **就从我们目前所在的 $st$ 这里开始吧，一直到位于 $ed$ 的白玉楼，** 紫会带我们穿过结界进入幻想乡的，现如今，幻想乡倒是开满了樱花， **大概有 $n$ 个地方适合赏樱呢，** 我跟紫说好了， **利用空间的裂缝互相连接了一些赏樱的地点，也包括我们所在的 $st$ 和位于 $ed$ 的白玉楼在内，这一共有 $m$ 条裂缝，不过每一条裂缝都是单向的，** 这一点小事，她很爽快地答应了，所以我们可以利用这些裂缝在两处适合赏樱的地点快速移动呢。无论实际距离有多远， **在由裂缝连接的两处地点移动所消耗的时间都是小到可以忽略的，** 这可是「操纵境界程度」的能力哦。”    “ 不过啊，樱花可需要仔仔细细地观赏呢，你觉得，给妖梦带回去一些是不是会很好呢？她每天还是很辛苦的啦…… 当然了，**赏樱和采摘樱花会需要一些时间，** 你会有耐心的，对吧？当然啦，即便是对于同一处地点， **如果从不同的地点前往的话，** 心境可是会不一样的哟，这样，**赏樱和采摘樱花的时间，也会是不同的，在这一处地点所需要消耗的时间是此处原本预计的时间 $t_1$ 与上一处地点原本预计的时间 $t_2$ 的平均值 \(向下取整\) 。** ”    “ 当从一处地点前往白玉楼的时候，**我需要一些时间来整理采摘的樱花，** 毕竟是要给妖梦的礼物呢。 **与先前在两处赏樱地点所需要的时间的规律相同，** 只不过，白玉楼现在可没有樱花哟， **所以在白玉楼赏樱的时间是 $0$ 。** ”    “当然，同样的， **我们现在所在的 $st$ 处所需要赏樱的时间也是 $0$ 哦，** 这里可只有寒风呢…… **在第一处赏樱地点所需要的时间， 要跟 $0$ 作平均呢……** ”   “ 嘛，如果你实在是太饿了的话，我们自然是可以选择耗时最少的路线，早早地到达白玉楼啦……只是，多陪我一会，我会很高兴的，毕竟有人同行的机会可是很少呢，至少， **是耗时第 $k$ 少的路线，** 好嘛？”  幽幽子和yhy相遇场景belike：↑ ~~实在写不动tag了所以请假装这里是山理工拿外卖的地方~~ ### 省流：   存在 $n$ 个点和 $m$ 条有向边，每个点含有点权，并且该点实际点权为当前点的预期点权与上一个经过的点的语气点权的平均值（向下取整）， 求 $st$ 点到 $ed$点的第 $k$ 短路。

第一行输入两个正整数 $n$ 和 $m$ ，分别表示所有地点的数量、连接两个地点之间的裂缝的数量。 接下来一行，共 $n$ 个正整数，表示每个地点预计需要花费的时间 $t_i$ $(1≤ i≤ n)$ ，输入保证 $st$ 点和 $ed$ 点的 $t_i$ 为 $0$ 。 接下来 $m$ 行，每行 $2$ 个正整数 $u$ 、$v$ ，表示地点 $u$ 向地点 $v$ 之间连接了一条裂缝。 接下来一行输入两个正整数 $st$ 和 $ed$ ，表示起始点的位置和终点的位置。 最后一行输入一个正整数 $k$ ，表示幽幽子所期望的耗时第 $k$ 少的路线。

输出一个正整数，表示所需要时间第 $k$ 少的路线所需要消耗的时间，如果没有第 $k$ 短的路径，则输出 `Saigyouji Yuyuko : o shi i.`

对于 $100\%$ 的数据， $1≤n≤10^3$ ，$1≤m≤10^5$ ， $ 1≤k≤100$ ,   $1 ≤st,ed≤ n\ (\ st\ ≠\ ed\ )$ , $0 ≤u,v≤10^8 $ . 图不保证联通，且存在环 . 十分感谢信风吹絮小姐对本题的指导和测试点数据的帮助！