问题描述

某国家流通有 $N$ 种货币，编号 $1 \sim N$。

该国家设有 $M$ 个货币兑换点，每个兑换点提供两种货币之间的兑换业务。

每个兑换点都自行设定货币兑换汇率以及服务费。

每个兑换点的基本信息可以用 $6$ 个数字 $A,B,R_{AB},C_{AB},R_{BA},C_{BA}$ 来描述，表示该兑换点提供第 $A$ 种货币和第 $B$ 种货币之间的相互兑换，并且从 $A$ 兑换到 $B$ 的兑换汇率为 $R_{AB}$，服务费为 $C_{AB}$，从 $B$ 兑换到 $A$ 的兑换汇率为 $R_{BA}$，服务费为 $C_{BA}$。

$A$ 到 $B$ 的兑换汇率就是 $1$ 单位 $A$ 货币可以换得的 $B$ 货币的数量。

服务费必须在兑换之前，先行从来源货币处扣除。

例如，如果从 $A$ 兑换 $B$ 的兑换汇率为 $29.75$，服务费为 $0.39$，则用 $100$ 元 $A$ 货币可以兑换 $(100 - 0.39) * 29.75 = 2963.3975$ 元 $B$ 货币。

一个商人目前手上有 $V$ 元 $S$ 货币，他想要通过先将自己手中的钱进行辗转兑换，最终再次换回 $S$ 货币的方式，让自己手中的钱变得更多。

请你判断他能否做到。

输入格式

第一行包含四个数字 $N,M,S,V$。

接下来 $M$ 行，每行包含 $6$ 个数字 $A,B,R_{AB},C_{AB},R_{BA},C_{BA}$。

输出格式

如果可以做到让钱变多，则输出 YES，否则输出 NO。

数据范围

$1 \le S \le N \le 100$,
$1 \le M \le 100$,
$0 \le V \le 1000$,
汇率取值范围 $[10^{-2},10^2]$，
服务费取值范围 $[0,100]$。

输入样例：

3 2 1 20.0
1 2 1.00 1.00 1.00 1.00
2 3 1.10 1.00 1.10 1.00

输出样例：

YES