坐标线上有n只狗,第i只狗在点xi。另外,直线上有m碗食物,每碗在直线uj上的坐标和时间tj已知,之后碗中的食物就会冷却并变得无味。这意味着,如果狗在严格大于 tj 的时间跑向碗,那么食物将已经冷却并且狗不会吃它。
假设每只狗以速度1奔跑,求最多能吃的狗数量。假设狗会跑向你指给它们的碗。两只或更多的狗不能从同一个碗里吃东西。
狗可以互相经过,也就是说,如果其中一只停下来吃东西,另一只可以经过它去吃另一个碗。
输入
第一行包含一对整数 n 和 m (1 ≤ n, m ≤ 200 000) — 分别是狗和碗的数量。
第二行包含 n 个整数 xi ( - 109 ≤ xi ≤ 109) — 第 i 只狗的坐标。
接下来的 m 行包含整数对 uj 和 tj ( - 109 ≤ uj ≤ 109, 1 ≤ tj ≤ 109) — 分别是第 j 个碗的坐标和其中食物冷却的时间。
保证没有两只狗在同一点。两个碗也不能位于同一点。
输出
打印一个整数a——可以吃的狗的最大数量。
示例
输入 #1
5 4 -2 0 4 8 13 -1 1 4 3 6 3 11 2
输出 #1
4
输入 #2
3 3 -1 3 7 1 1 4 1 7 1
输出 #2
2
输入 #3
4 4 20 1 10 30 1 1 2 5 22 2 40 10
输出 #3
3
注意
在第一个示例中,第一只狗将向右跑到第一个碗,第三只狗将立即开始从第二个碗吃东西,第四只狗将向左跑到第三个碗,第五只狗将向左跑到第四个碗。