Pharmacist's Reagent Mixing Challenge

Pharmacist Luo is an expert in liquid explosives. In his laboratory, he has \(n\) types of liquid reagents. Each reagent is made up of four chemical elements, namely \(\alpha,\;\beta,\;\gamma,\;\delta\). For the \(i\)-th reagent, the amounts (in grams) of these elements are \(a_i,\; b_i,\; c_i,\; d_i\) respectively.

Customers make two kinds of requests:

1. The exact blend request: they require a reagent mixture that contains exactly \(A,\; B,\; C,\; D\) grams of \(\alpha,\; \beta,\; \gamma,\; \delta\) respectively.
2. The explosive blend request: given environmental parameters \(A, B, C, D\), a reagent is said to be explosive if for a mixture with amounts \(a, b, c, d\) one has \[ A\cdot a + B\cdot b + C\cdot c + D\cdot d \ge 0. \]

When mixing two reagents, Luo is allowed to take an arbitrary non-negative amount from each of the two available copies and mix them. (Note that using just one reagent is allowed by taking all mixture from the same reagent.)

Your task is to determine whether the requested operation can be achieved using at most two reagent types from the laboratory.

The input begins with an integer indicating the type of request: use 1 for an exact blend and 2 for an explosive blend.

inputFormat

The input format is as follows:

T
n
a1 b1 c1 d1
...
an bn cn dn
A B C D

Here, T is an integer representing the type of request (1 for the exact blend and 2 for the explosive blend). The next integer n denotes the number of reagent types. Then follow n lines each containing four integers \(a_i, b_i, c_i, d_i\). The last line contains four integers \(A, B, C, D\); for T=1 these represent the required amounts for the blend, and for T=2 they represent the environmental parameters.

outputFormat

Output a single line containing YES if the requested formulation can be achieved, otherwise output NO.

sample

1
3
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16

YES