Problem:

展覧会(Exhibition)

  あなたは，絵の展覧会を開催しようとしている．展覧会では，いくつかの絵を額縁に入れ，左から右に一列に並べて展示する．

  展覧会で展示する候補となる絵が$N$ 枚あり，1 から$N$ までの番号が付けられている．絵$i$ ($1 \leq i \leq N$) の大きさは$S_i$，価値は$V_i$ である．

  また，これらの絵を入れるための額縁が$M$ 枚あり，1 から$M$ までの番号が付けられている．額縁$j$ ($1 \leq j \leq M$) の大きさは$C_j$ である．額縁$j$ には，大きさが$C_j$ 以下の絵のみを入れることができる．1 枚の額縁には高々1 枚の絵しか入れることができない．

  展示する絵はすべて何らかの額縁に入っていなければならない．見栄えを良くするため，展示する絵は以下の条件を満たさなければならない：

左右に隣り合うどの2 枚の絵についても，右側の絵が入っている額縁の大きさは左側の絵が入っている額縁の大きさ以上である．

 左右に隣り合うどの2 枚の絵についても，右側の絵の価値は左側の絵の価値以上である．

  あなたは，できるだけ多くの絵を展示したい．

  展示候補の絵の枚数，額縁の枚数，及びそれらの大きさや価値が与えられたとき，展示する絵の枚数の最大値を求めるプログラムを作成せよ．

入力

  入力は以下の形式で標準入力から与えられる．

$N$ $M$
$S_1$ $V_1$
:
$S_N$ $V_N$
$C_1$
:
$C_M$

出力

  標準出力に，展覧会に展示する絵の枚数の最大値を1 行で出力せよ．

制約

$ 1 \leq N \leq 100 000$.

$ 1 \leq M \leq 100 000$.

$ 1 \leq S i \leq 1 000 000 000 (1 \leq i \leq N)$.

$ 1 \leq V_i \leq 1 000 000 000 (1 \leq i \leq N)$.

$ 1 \leq C_j \leq 1 000 000 000 (1 \leq j \leq M)$.

  
  

入出力例

  

入力例1 

3 4
10 20
5 1
3 5
4
6
10
4

出力例1

2

  この入出力例では，左から順に(絵2, 額縁2)，(絵1, 額縁3) と並べることで，2 枚の絵を展示することができる．3 枚以上の絵を展示することはできないので，2 を出力する．ここで，(絵$i$, 額縁$j$) は，額縁$j$に入った絵$i$ を表す．

入力例2

3 2
1 2
1 2
1 2
1
1

 出力例2

2

入力例3

4 2
28 1
8 8
6 10
16 9
4
3

出力例3

0

入力例4

8 8
508917604 35617051
501958939 840246141
485338402 32896484
957730250 357542366
904165504 137209882
684085683 775621730
552953629 20004459
125090903 607302990
433255278
979756183
28423637
856448848
276518245
314201319
666094038
149542543

出力例4

3

  
  

  情報オリンピック日本委員会作 『第18 回日本情報オリンピック(JOI 2018/2019) 本選』



Sample input:
3 4
10 20
5 1
3 5
4
6
10
4


Sample output:
2

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import array
from fractions import Fraction
import functools
import itertools
import math
import os
import sys


def main():
    N, M = read_ints()
    P = [(s, v) for s, v in [read_ints() for _ in range(N)]]
    C = [read_int() for _ in range(M)]
    print(solve(N, M, P, C))


def solve(N, M, P, C):
    P.sort(key=lambda p: (-p[1], -p[0]))
    C.sort(reverse=True)
    ci = 0
    for pi in range(N):
        if ci == M:
            break
        s = P[pi][0]
        if C[ci] >= s:
            ci += 1
    return ci


###############################################################################
# AUXILIARY FUNCTIONS

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()