题目描述

我们城市中有几个货币兑换点。假设每个兑换点专门从事两种特定货币的兑换，并只与这些货币进行兑换操作。可能有多个兑换点专门从事同一种货币对的兑换。每个兑换点都有自己的汇率，$A$ 到 $B$ 的汇率是 $1$ 单位的 $A$ 可以得到的 $B$ 的数量。此外，每个兑换点都有一定的手续费，这是您在进行兑换操作时必须支付的费用。手续费始终以源货币收取。

例如，如果您想在一个兑换点将 $100$ 美元兑换成俄罗斯卢布，该兑换点的汇率是 $29.75$，手续费是 $0.39$，您将得到 $(100 - 0.39) * 29.75 = 2963.3975$ 卢布。

您肯定知道，在我们的城市中，您可以使用 $N$ 种不同的货币。让我们为每种货币分配一个从 $1$ 到 $N$ 的唯一整数编号。然后，每个兑换点可以用 $6$ 个数字来描述：整数A和B - 它兑换的货币编号，以及RAB、CAB、RBA和CBA - 分别是 $A$ 兑换到 $B$ 和 $B$ 兑换到 $A$ 时的汇率和手续费。

尼克有一些 $S$ 货币的现金，并想知道他是否可以通过一些兑换操作来增加他的资本。当然，他希望最终将他的钱兑换回 $S$ 货币。帮助他回答这个难题。尼克在进行操作时必须始终保持非负的货币总额。

输入格式

输入的第一行包含四个数字：$N$ - 货币数量，$M$ - 兑换点数量，$S$ - 尼克拥有的货币编号，$V$ - 他拥有的货币单位数量。$1 \le S \le N \le100$, $1 \le M \le 100, V$是一个实数，$0 \le V \le 10^3$。

接下来的 $M$ 行每行包含6个数字 - 对应兑换点的描述 - 按照上述指定的顺序。数字之间由一个或多个空格分隔。

每个点的汇率 $rate$ 和手续费 $commission$ 都是实数，最多保留两位小数，$10^{-2}\le rate \le 10^2, 0 \le commission \le 10^2$。 让我们将某个兑换操作序列称为简单序列，如果在这个序列中没有重复使用任何兑换点。

输出格式

如果尼克可以增加他的财富，输出YES，否则输出NO到输出文件。

样例

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