题目描述

这是 2017 年的冬天。（又到了白色相簿的季节 2333）
滑完雪之后， ことり 突然想吃点心啦！wtnap 收到短信时正好在甜品店，于是 wtnap 决定买好了带去给她。不幸的是，日本的冬天经常下雪，今天也不例外。

秋叶原共有 $n$ 个地点，分别编号为 $1,2,\ldots,n$ 。点心店所在地点的编号是 $s$，ことり家的编号是 $t$ 。
有 $m$ 条道路连接这些地点，它们的长度分别为 $w_i\:\textrm{m}$ 。为了便于绘制地图，秋叶原的道路规划保证每条道路严格地连接两个不同的地点，并且不会有两条道路连接的两个地点相同。
雪太大，公共交通系统已经停摆了，所以你得走路过去。你的走路速度是 $1\:\textrm{m/s}$ 。
开始时，地点 $i$ 的积雪深度为 $h_i\:\textrm{mm}$ 。每秒钟地面上积雪的厚度会增加 $q\:\textrm{mm}$。每个地点都有一个步行的极限雪深 $l_i\:\textrm{mm}$ ，如果到达此地时此地的雪深 $> l_i$，wtnap 会被困在这个点，无法成功地走到 ことり 家。
不考虑点心店和 ことり 家的雪。ことり 想在 $g$ 秒内吃到点心， wtnap 要越快越好。如果在 $g$ 秒之内， wtnap 无法到达 ことり 的家，或者 wtnap 被困在路上了，那么 ことり 会把 wtnap 变成她的点心。

输入格式

第 $1$ 行 $6$ 个整数，空格隔开，分别代表 $n,m,s,t,g,q$ 。
以下 $n$ 行，每行 $2$ 个整数，空格隔开，分别表示这个地点的 $h_i$ 和 $l_i$ 。
以下 $m$ 行，每行 $3$ 个整数，空格隔开，分别表示这条路连接的两个地点 $u, v$ 和这条路的长度 $w_i$ 。

输出格式

如果 wtnap 变成了 ことり 的点心那么输出一行字符串 $\texttt{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!

数据范围与提示

特殊约定

没有测试数据与样例相同。
对于 $40\%$ 的数据， $q = 0$ 。在 $q=0$ 的数据中，有 $50\%$ 的数据 $w_i < l_i (1\le i\le n)$ 。
对于所有数据，$1 \le s, t \le n , 0 \le g, q \le 10^9 , 0 \le w_i \le l_i \le 10^9$ 。

数据范围