← 返回题目列表

AtCoder · code_festival_morning_easy_d

D. 枕头选择

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

問題文

CODE FESTIVAL 2014 参与者中,n 人们试图住在酒店里。

酒店有 有 m 个房间和房间 i 有一个高度 有一个 a_i 枕头。 酒店房间不是很宽敞,所以1 一间房间最多有 1 只有人可以过夜。 每个参与者都对枕头的高度有偏好。 第i 位参与者是 x_i 以上 y_i 我更喜欢以下高度的枕头:

如果您分配一个酒店房间,以便尽可能多的参与者可以使用他们最喜欢的枕头,请找出可以使用他们最喜欢的枕头的人数。


入力

输入按以下格式给出。

n m
x_1 y_1
...
x_n y_n
a_1
...
a_m
  • 1 行是一个整数,表示过夜人数。 n (1 \leq n \leq 100{,}000)和一个表示酒店房间数量的整数。 给出了 m (1 \leq m \leq 100{,}000)。
  • 继续 n 行给出了每个参与者对枕头高度的偏好范围。
  • x_i, y_i (1 \leq x_i \leq y_i \leq 100{,}000) 是i 第一位客人 x_i 以上 y_i 表示您更喜欢低于高度的枕头。
  • 继续 m 行给出了每个酒店房间的枕头高度。
  • a_i (1 \leq a_i \leq 100{,}000) 是i 第号房间的枕头高度是 a_i 。

出力

在分配酒店房间以便尽可能多的参与者可以使用他们喜欢的枕头时,可以使用他们喜欢的枕头的人数为 1 行输出。

在末尾使用换行符,并且不要包含不必要的字符或空行。


入力例1

3 3
1 2
2 3
3 4
1
2
3

出力例1

3

入力例2

3 3
1 2
2 3
3 4
2
4
5

出力例2

2

入力例3

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

出力例3

3