Comet OJ

C1762 [国庆欢乐赛]两排房子

内存限制：256 MB 时间限制：1000 ms

题目描述

在马路两侧有两排房子，分别有 $n$ 栋和 $m$ 栋。左侧第 $i$ 栋房子占用的区间(闭区间)为 $[Lx_i, Ly_i]$，右侧第 $i$ 栋房子占用的区间 (闭区间)为 $[Rx_i, Ry_i]$。每一侧房子是不重叠的(即每一侧的区间不会相交)，但可能紧挨着 (两个区间有一个交点)。

左边的第 $i$ 栋房子和右边的第 $j$ 栋房子被称为「对门」当且仅当 $[Lx_i, Ly_i]$ 和 $[Rx_j, Ry_j]$ 至少有一个交点。 (同一侧的任两栋房子都不是「对门」)

现在，给你这 $n+m$ 个房子的信息，你需要给求出有多少对房子为「对门」关系。

输入格式

第一行两个整数 $n, m$，表示两边的房子数量。

接下来 $n$ 行，每行两个整数 $Lx_i, Ly_i$，表示道路左边一栋房子的信息。

接下来 $m$ 行，每行两个整数 $Rx_i, Ry_i$，表示道路右边一栋房子的信息。

  • $1 \le n, m \le 2 \times 10^5$
  • $-10^9 \le Lx_i < Ly_i \le 10^9$
  • $Ly_i \le Lx_{i+1}$
  • $-10^9 \le Rx_i < Ry_i \le 10^9$
  • $Ry_i \le Rx_{i+1}$

输出

输出一行一个整数表示答案。

样例

样例输入 1

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

样例输出 1

5

提示