Migrated from Lutece 2970 炮弹人向前冲！

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

小橘子正在无聊的刷着小视频，那种经常可见的小游戏广告又双叒叕映入眼帘。这次，她实在忍不住好奇，点了进去。

现在小橘子来到一个炮弹人的世界，她有一门大炮可以每秒发射任意多的蓝色炮弹人，面前有 $m$ 条路，将 $n$ 座城堡连接起来，炮弹人由于不是很聪明的样子，他们只会沿着路的方向一直向前冲。路有宽有窄，第 $i$ 条路每秒只能通过$c_i$ 个炮弹人，这 $n$ 个城堡中有一个是她的蓝色炮弹人的大本营 $s$ （也是她的大炮所在的地方），有一个是红色炮弹人的大本营 $t$，红色炮弹人的大本营有 $H$ 的血量，他每秒会生成 $k$ 个红色炮弹人在周围守护他的大本营（为了简化，我们假设这里的红色炮弹人不会移动），一个蓝色炮弹人可以和一个红色炮弹人抵消，或者轰击到红色炮弹人的大本营后马上消失，并会使其减少一滴血量。她首先侦察获得了整个地图，虽然战斗还没开始，但小橘子已经迫不及待的想要知道最少需要多少秒才能击败红色炮弹人，如果能击败，输出至少需要多少秒（整数），如果不能击败，则输出 $-1$。（每次所有炮弹人都会在一秒的开始全部瞬间生成完毕）

Tips：这里为了方便不输出小数，我们将时间向上取整，假设实际需要 $3.4s$ 就能刚好击败红色炮弹人，则输出 $4s$ 作为答案，如果刚好需要 $4s$ 击败红色炮弹人，则也输出 $4s$ 作为答案。

Input

第一行两个整数 $n,m(2\leq n\leq10000,1\leq m\leq 100000)$ 表示 $n$ 座城堡，$m$ 条路。

第二行两个整数 $H,k (1 \leq H\leq 10^9,1 \leq k\leq 10000)$ 表示红色炮弹人的城堡血量和每秒生成的红色炮弹人个数（初始双方炮弹人个数均为 $0$）。

接下来 $m$ 行描述了整个地图，每行三个整数$a,b,c(1\leq a,b\leq n,0\leq c\leq 10^4)$ 表示一条从城堡 $a$ 连接到城堡 $b$ 的一条单向路，每秒可以通过 $c$ 个炮弹人。

最后一行两个数字 $s,t(1\leq s,t\leq n,\ s\not=t)$ 表示蓝色炮弹人的城堡编号和红色炮弹人的城堡编号。

Output

如果小橘子可以击败红色炮弹人，则按向上取整输出至少需要多少秒，否则输出 $-1$。

Samples

4 5 
100 30
4 2 30
4 3 20
2 3 20
2 1 30
1 3 30
4 3

5

Note

可以看出，从 $4$ 号城堡最多每秒能发射 $50$ 个蓝色炮弹人到 $3$ 号红色炮弹人的城堡，该城堡每秒生成 $30$ 个红色炮弹人保护，则蓝色炮弹人每秒对其造成 $20$ 点伤害，总共 $100$ 血量，则至少需要 $5s$，所以答案为 $5$ 。

Resources

2023 UESTC ICPC Training for Graph