该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

这是2017年的冬天。（又到了白色相簿的季节2333）

滑完雪之后，ことり突然想吃点心啦！于是她去了甜品店。

日本的冬天经常下雪。不幸的是，今天也是这样，每秒钟雪的厚度会增加 $q$ 毫米。

秋叶原共有 $n$ 个地点，编号从 $1$ 到 $n$。每个地点在开始的时候的积雪高度为 $h_i$。

有 $m$ 条双向道路连接这些地点，它们的长度分别为 $w_i$ 米。

雪太大，公共交通系统已经停摆了，所以ことり得走路回家。她走路的速度是 $1\text{m/s}$。

为了方便地图的绘制，秋叶原的道路规划使得每条道路严格地连接两个不同的地点，并且不会有两条道路连接的地点相同。

每个地点都有一个极限雪高 $l_i$，单位是毫米，如果到达这个地点的时候，这里的雪的高度高于 $l_i$ 则会被困在这个点走不出去，无法成功地走到ことり家。

点心店这个地点的编号是 $s$，ことり家的编号是 $t$。

不考虑点心店和ことり家的雪。

ことり想在 $g$ 秒内回到家吃点心，越快越好。如果在 $g$ 秒之内，ことり无法到家，或者她被困在路上了，那么ことり会把 wtnap 变成她的点心 ( ・ 8 ・ )

输入格式

第 $1$ 行 $6$ 个整数，空格隔开，分别代表 $n$，$m$，$s$，$t$，$g$，$q$。

以下 $n$ 行，每行 $2$ 个整数，空格隔开，分别表示这个地点的 $h_i$ 和 $l_i$。

以下 $m$ 行，每行 $3$ 个整数，空格隔开，分别表示这条路连接的两个地点 $u, v$ 和这条路的长度 $w_i$。

输出格式

输出 $1$ 行 $1$ 个整数，表示到达ことり家的最短用时。

如果 wtnap 变成了ことり的点心那么输出 wtnap wa kotori no oyatsu desu!。

2 1 1 2 10 1
1 10
3 10
1 2 6

6

5 6 2 5 10 1
1 10
1 10
1 10
1 10
1 10
1 5 9
1 3 9
2 4 1
2 5 9
3 4 1
3 5 6

8

5 6 2 5 10 1
1 10
1 10
10 10
1 10
1 10
1 5 9
1 3 9
2 4 1
2 5 11
3 4 1
3 5 6

wtnap wa kotori no oyatsu desu!

提示

对于 $0\%$ 的数据，与样例一模一样；
对于 $40\%$ 的数据，$q = 0$。
对于上一行中 $50\%$ 的数据，所有 $w_i < l_i$。
对于 $100\%$ 的数据，$1 \le s, t \le n$；$0 \le g, q \le 10^9$；$0 \le w_i \le l_i \le 10^9$。

数据范围与约定

测试点编号	$n$	$m$	其他约定
$1,2,3,4$	$\le 10$	$\le 20$	奇数点 $q$ 为 $0$，$w_i < l_i$
$5,6,7,8$	$\le 100$	$\le 500$
$9,10,11,12$	$\le 1000$	$\le 5000$	奇数点 $q$ 为 $0$
$13,14,15,16$	$\le 10000$	$\le 50000$
$17,18,19,20$	$\le 100000$	$\le 500000$	无