問題
背景
与兔子王国建立友好关系的鳗鱼王国,这次决定进军宇宙。目标是建造鳗鱼宇宙站。然而,由于无数的小行星阻碍,无法占据广阔的空间。因此国王决定使用激光炮,把阻碍的小行星彻底摧毁。
課題
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