H - Asteroids2
Editorial
/


Time Limit: 2 sec / Memory Limit: 256 MB
問題
背景
うさぎ王国と友好関係を築いたうなぎ王国は,今度は宇宙に進出することにした.目標はうなぎ宇宙ステーションの建設である.しかしながら,無数の小惑星に邪魔をされ,広大な空間を占有することができない.そこで王様はレーザー砲を使い,邪魔な小惑星を破壊し尽くすことにした.
課題
N \times N の二次元格子上に M 個の小惑星がある.縦方向(x軸に垂直)もしくは横方向(y軸に垂直)にレーザーを打つことで全ての小惑星を破壊したい.発射されたレーザーは一直線に進み,途中の小惑星を全て貫通してダメージを与える.全てのレーザーは同時に発射され,その出力には,x軸に垂直に直線(x=i)に沿って最大で pi,y軸に垂直に直線(y=j)に沿って最大で qj の非負整数値を設定することが出来る.小惑星 k は,位置 (xk,yk) にあり,合計出力が ak 以上あれば破壊されるが,合計出力が bk より大きくなると爆発して非常に危険である.どの小惑星も爆発させることなく,全ての小惑星を破壊できるか判定せよ.
配点
200
入力
入力は以下の形式で与えられる.
N M p1 ... pN q1 ... qN x1 y1 a1 b1 ... xM yM aM bM
制約
入力中の各変数は以下の制約を満たす.
- 1 \leq N \leq 1000 (=103)
- 1 \leq M \leq 100000 (=105)
- 1 \leq pi, qi \leq 1000000 (=106)
- 1 \leq xi, yi \leq N
- (xi, yi) \neq (xj, yj) (i \neq j)
- 1 \leq ak \leq bk \leq 2000000 (=2 \times 106)
出力
どの小惑星も爆発させることなく,全ての小惑星を破壊することが可能ならば "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