题目描述

A 国内有 $n$ 种货币与 $m$ 个货币兑换站，第 $i$ 个货币兑换站会以 $v_{i,1}$ 的汇率以及 $d_{i,1}$ 的手续费将第 $a_i$ 种货币兑换为第 $b_i$ 种货币，或是以 $v_{i,2}$ 的汇率以及 $d_{i,2}$ 的手续费将第 $b_i$ 种货币兑换为第 $a_i$ 种货币。具体的，你可以在第 $i$ 个货币兑换站把 $x$ 单位的货币 $a_{i}$ 兑换为 $(x-d_{i,1})\cdot v_{i,1}$ 单位的货币 $b_i$，反之同理。

现在你初始拥有 $s$ 单位的货币 $k$，请问是否可以通过若干次兑换得到超过 $s$ 单位的货币 $k$。

输入格式

第一行四个数 $n,m,k,s$，其中 $s$ 是实数，其余都是整数。

接下来 $m$ 行，每行先是两个整数 $a_i,b_i$，接下来四个实数 $v_{i,1},d_{i,1},v_{i,2},d_{i,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

数据规模与约定

对于 $100\%$ 的数据，$1\leq s\leq n,m\leq 100$，$0.01\leq v_i\leq 100$，$0\leq d_i\leq 100$，$0\leq v\leq 10^3$。