描述
我们城市中有多个货币兑换点。假设每个兑换点专门兑换两种特定货币，并且只进行这两种货币的兑换操作。可能存在多个兑换点专门兑换同一对货币。每个兑换点有自己的汇率，将货币$A$兑换为货币$B$的汇率是指用$1$单位$A$能兑换多少单位$B$。此外，每个兑换点还会收取一定的手续费，手续费在兑换时从源货币中扣除。

例如，如果你想在某个兑换点将$100$美元（USD）兑换为俄罗斯卢布（RUR），该点的汇率是$29.75$，手续费是$0.39$，那么你将得到$(100 - 0.39) \times 29.75 = 2963.3975$卢布。

已知城市中有$N$种不同的货币，编号为$1$到$N$的整数。每个兑换点可以用$6$个数字描述：整数$A$和$B$表示兑换的两种货币，实数$R_{AB}$、$C_{AB}$、$R_{BA}$、$C_{BA}$分别表示从$A$兑换到$B$的汇率和手续费，以及从$B$兑换到$A$的汇率和手续费。

Nick手上有一些货币$S$，他想知道是否可以通过一系列兑换操作最终增加他的本金（最终货币仍为$S$）。在操作过程中，他的货币金额必须始终为非负数。

输入
第一行包含四个数字：$N$（货币种类数）、$M$（兑换点数）、$S$（Nick持有的货币编号）和$V$（持有的货币数量）。接下来的$M$行每行包含$6$个数字，描述一个兑换点，顺序为$A$、$B$、$R_{AB}$、$C_{AB}$、$R_{BA}$、$C_{BA}$。数字之间由一个或多个空格分隔。
$1 \leq S \leq N \leq 100$
$1 \leq M \leq 100$
$V$为实数，$0 \leq V \leq 10^3$
汇率和手续费为实数，最多保留两位小数，$10^{-2} \leq \text{rate} \leq 10^2$，$0 \leq \text{commission} \leq 10^2$

假设在任意简单的兑换操作序列（即同一兑换点最多使用一次）中，本金在操作结束时的数值与初始时的比值不超过$10^4$。

输出
如果Nick能增加他的本金，输出YES，否则输出NO。

输入数据 1

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

输出数据 1

YES

来源
Northeastern Europe $2001$, Northern Subregion