You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

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

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

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

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

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

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

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

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

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

输入格式

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

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

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

输出格式

输出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%的数据，所有wi < li。
对于100%的数据，1 ≤ s, t ≤ n; 0 ≤ g, q ≤ 10^9; 0 ≤ wi ≤ li ≤ 10^9。