题目描述

我们的城市有M个货币兑换点。每个兑换点只能在两种货币之间互相兑换。同一对货币可能有多个兑换点。每个兑换点都有自己的汇率。A到B的汇率是指1元钱的A类货币可以兑换的B类货币的金额。每个兑换点对于每笔兑换业务都会收取一个固定的佣金。佣金始终以兑换前的货币进行收取。例如，如果某个兑换点美元到俄罗斯卢布的汇率是29.75，每笔兑换收取0.39元的佣金，那么如果您有100美元，要在该兑换点全部换成卢布的话，您可以兑换到(100-0.39) * 29.75 = 2963.3975元卢布。

我们城市可以处理N种不同的货币，让我们为每种货币分配一个1...N的唯一编号。然后用6个数字来描述每个兑换点：A，B，RAB，CAB，RBA，CBA，表示该兑换点可以使用货币A兑换货币B，也可以使用货币B兑换货币A，RAB代表A到B的汇率，CAB代表每笔A到B的兑换业务的手续费，RBA代表B到A的汇率，CBA代表每笔B到A的兑换业务的手续费。

尼克拥有S类货币C元，他想知道是否可以在进行一些兑换操作后是自己的C元钱增值。当然，它希望最后还是将钱兑换成S类货币。请你帮他回答这个难题。（尼克在进行兑换时必须拥有非负数的资金）

输入格式

第一行：4个空格分隔的数字：N-货币数量，M-兑换点数量，S-尼克开始时拥有的货币的种类，C-尼克开始拥有的S类货币的数量。
接下来M行：每行6个数字：A, B, RAB, CAB, RBA, CBA，代表一个兑换点的信息，含义如题目描述中所述。
上述输入中N、M、S、A、B是整数，C是一个浮点数，RAB、CAB、RBA和CBA是包含两位小数的浮点数。

输出格式

一行：如果尼克可以使自己的金钱增值输出"YES"，否则输出“NO”。

样例数据

input

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

output

YES

数据范围

1 ≤ S ≤ N ≤ 100，1 ≤ M ≤ 100，0 ≤ C ≤ 10^3，0.01 ≤ RAB, RBA ≤ 100，0 ≤ CAB, CBA ≤ 100。