問題

背景

うさぎ王国と友好関係を築いたうなぎ王国は，今度は宇宙に進出することにした．目標はうなぎ宇宙ステーションの建設である．しかしながら，無数の小惑星に邪魔をされ，広大な空間を占有することができない．そこで王様はレーザー砲を使い，邪魔な小惑星を破壊し尽くすことにした．

課題

N \times N の二次元格子上に M 個の小惑星がある．縦方向(x軸に垂直)もしくは横方向(y軸に垂直)にレーザーを打つことで全ての小惑星を破壊したい．発射されたレーザーは一直線に進み，途中の小惑星を全て貫通してダメージを与える．全てのレーザーは同時に発射され，その出力には，x軸に垂直に直線(x=i)に沿って最大で p_i，y軸に垂直に直線(y=j)に沿って最大で q_j の非負整数値を設定することが出来る．小惑星 k は，位置 (x_k,y_k) にあり，合計出力が a_k 以上あれば破壊されるが，合計出力が b_k より大きくなると爆発して非常に危険である．どの小惑星も爆発させることなく，全ての小惑星を破壊できるか判定せよ．

配点

200

入力

入力は以下の形式で与えられる．

N M
p1 ... pN
q1 ... qN
x1 y1 a1 b1
...
xM yM aM bM

制約

入力中の各変数は以下の制約を満たす．

• 1 \leq N \leq 1000 (=10³)
• 1 \leq M \leq 100000 (=10⁵)
• 1 \leq p_i, q_i \leq 1000000 (=10⁶)
• 1 \leq x_i, y_i \leq N
• (x_i, y_i) \neq (x_j, y_j) (i \neq j)
• 1 \leq a_k \leq b_k \leq 2000000 (=2 \times 10⁶)

出力

どの小惑星も爆発させることなく，全ての小惑星を破壊することが可能ならば "yes" ，不可能ならば "no" を一行に出力せよ．

入力例1

2 3
1 2
3 4
2 1 3 5
1 2 3 4
2 2 6 6

入力例1に対する出力例

yes

下図のようにレーザーの出力を設定すれば，全ての小惑星を安全に破壊できる．

図 1

入力例2

2 3
1 2
3 4
2 1 1 1
1 2 2 3
2 2 5 7

入力例2に対する出力例

no