← 返回题目列表

Codeforces · 648/D

D. 狗和碗

中文机器翻译题面 查看原题

坐标线上有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

注意

在第一个示例中,第一只狗将向右跑到第一个碗,第三只狗将立即开始从第二个碗吃东西,第四只狗将向左跑到第三个碗,第五只狗将向左跑到第四个碗。