3991. 选择题

单点时限: 1.0 sec

内存限制: 512 MB

在 2011 年 NOIP 提高组的初赛题中,Cuber QQ 遇到了这个选择题:

公元 1956 年,肖克利、巴丁和布拉顿共同获得了:

  • A. 诺贝尔物理学奖
  • B. 约翰·冯·诺依曼奖
  • C. 图灵奖
  • D. 高德纳奖

冯·诺依曼奖是 1990 年成立的,图灵奖是 1966 年设立的,高德纳奖是 1996 年设立的。因此答案选 A。

如今 Cuber QQ 想要出很多道这样的题。在出题之前,他希望你帮他预估一下工作量。

Cuber QQ 会给你 $n$ 个著名历史人物的资料。第 $i$ 个历史人物的资料如下(假设他/她的名字是 $i$ 神):

  • 出生年份为 $a_i$。
  • 以他的名字命名的奖项的设立年份为 $b_i$($a_i < b_i$)。即,$b_i$ 年是第一届$i$ 神奖。该奖项为一年一届。

此外,Cuber QQ 还会给你 $m$ 个有意义的年份,记作 $d_1,\ldots,d_m$。

一道选择题形如:

公元 $d_t$($1\le t\le m$) 年,第 $e$($1\le e\le n$) 个著名历史人物获得了:

  • A. $A$ 神奖
  • B. $B$ 神奖
  • C. $C$ 神奖
  • D. $D$ 神奖

我们用元组 $(t,e,A,B,C,D)$ 表示选择题。

Cuber QQ 的出题有一些限制:

  • $A<B<C<D$,即四个选项互不相同;
  • $a_e<d_t$,即历史人物必须在颁奖时间前出生;
  • $x\in{A,B,C,D}$ 中有且仅有一个选项满足: $b_x\le d_t$。即颁奖时间在奖项成立时间之后。

Cuber QQ 认为两个题是不同的当且仅当有序元组 $(t,e,A,B,C,D)$ 存在一位不同。

Cuber QQ 想知道一共能出多少道不一样的选择题,对 $114514$ 取模后输出。

输入格式

第一行两个数 $n,m$($1\le n,m\le 10^5$);

接下来一行 $n$ 个数表示 $a_1,\ldots,a_n$($1\le a_i\le 10^9-1$)。

接下来一行 $n$ 个数表示 $b_1,\ldots,b_n$($a_i< b_i\le 10^9$)。

接下来一行 $m$ 个数表示 $d_1,\ldots,d_m$($1\le d_i\le 10^9$)。

输出格式

输出一行表示答案。

样例

Input
4 1
1 2 3 4
2 3 4 5
2
Output
1

提示

Cuber QQ 出的题目为:

公元 $2$ 年,第 $1$ 个著名历史人物获得了:

  • A. $1$ 神奖
  • B. $2$ 神奖
  • C. $3$ 神奖
  • D. $4$ 神奖

答案是 $A$。即我获得我自己设立的奖项。

174 人解决,261 人已尝试。

203 份提交通过,共有 1440 份提交。

3.8 EMB 奖励。

创建: 4 月,3 周前.

修改: 4 月,3 周前.

最后提交: 4 周前.

来源: EOJ Monthly 2020.11

题目标签