Description

有几个货币兑换点，每个点只能兑换两种特定货币。可以有几个专门针对同一种货币的兑换点。每个兑换点都有自己的汇率，货币$A$到货币$B$的汇率是$A$兑换$B$的数量。此外，每个交换点都有一些佣金，即必须为交换操作支付的金额。佣金始终以源货币收取。

例如，如果想在兑换点用$100$美元兑换俄罗斯卢布，而汇率为$29.75$，佣金为$0.39$，则将获得$(100 - 0.39)×29.75=2963.3975RUR$。可以处理 $N$ 种不同的货币。货币编号为$1～N$ 。对每个交换点都用$6$个数字来描述：整数$A$ 和$B$ （交换的货币类型），$以及R_{AB} 、C_{AB} 、R_{BA}和C_{BA} （分别表示交换$A$到$B$和$B$到$A$时的汇率和佣金）。$

尼克有一些货币 $S$ ，并想知道他是否能在一些交易所操作之后增加他的资本。当然，他最终想要换回货币$S$ 。在进行操作时所有金额都必须是非负数。

Format

Input

输入的第 $1$行包含$4$个数字：$N$ 表示货币类型的数量，$M$ 表示交换点的数量，$S$ 表示尼克拥有的货币类型，$V$ 表示他拥有的货币数量。以下$M$ 行，每行都包含$6$个数字，表示相应交换点的描述。数字由一个或多个空格分隔。$1≤S ≤N ≤100，1≤M ≤100$，$V$是实数，$0≤V≤10^3$ 。汇率和佣金在小数点后至多有两位，$10^{-2} ≤汇率≤10^2$ ，$0≤佣金≤10^2$ 。

Output

如果尼克可以增加他的财富，则输出“YES”，在其他情况下输出“NO”。

Samples

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

Limitation

1s, 1024KiB for each test case.

来源

POJ1860