AtCoder国家拥有编号为$1$至$N$的$N$个城市和编号为$1$至$M$的$M$条铁路。

铁路$i$连接着城市$A_i$和城市$B_i$之间，每到时间是$K_i$的倍数时，从双方城市分别开往另一城市的列车就会发车。这趟列车从出发到到达需要$T_i$的时间。

你现在在城市里。在乘坐时刻$0$美元或以后城市$X$发车的列车开始移动时，请寻求最快什么时候能到达城市$Y$。如果无法到达城市$Y$，请报告这件事。

但是，由于换乘所需的时间可以忽略，所以在任何城市，都可以换乘与你乘坐的列车到达时间同时发车的其他列车。

输入格式

输入以以下形式由标准输入给出。

$N$ $M$ $X$ $Y$ $A_1$ $B_1$ $T_1$ $K_1$ $\vdots$ $A_M$ $B_M$ $T_M$ $K_M$

输出格式

输出能到达城市$Y$的最早时间。但是，如果无法到达城市$Y$，请代为输出-1。