题意描述

你将举办一个画展。在展览中，你需要将一些画放入一些画框中并摆放成一排。

展览有 $N$ 幅候选画，编号从 $1$ 到 $N$。画 $i ( 1 \le i \le N)$ 具有大小 $S_i$ 和美观度 $V_i$。

另外，有 $M$ 个候选画框，编号从 $1$ 到 $M$。画框 $j ( 1 \le j \le M)$ 的大小为 $C_j$。

只有大小不超过 $C_j$ 的画才能放入画框 $j$ 中。每个画框中最多只能放一幅画。每幅要展出的画都必须放在一个画框中。

考虑到美观因素，展出的画必须满足以下条件：

对于任意两幅相邻的画，右边的画框大小不小于左边的画框
对于任意两幅相邻的画，右边的画的美观度不小于左边的画的美观度

你需要求出你最多能展出多少幅画。

输入格式

第一行两个整数 $N$ 和 $M$。

接下来 $N$ 行，第 $i$ 行为两个整数 $S_i$ 和 $V_i$。

接下来 $M$ 行，第 $i$ 行为一个整数 $C_i$。

输出格式

输出一行一个整数，表示你最多能展出的画的数量。

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

数据范围和约定

对于所有输入数据，有 $1 \le N, M \le 10^5, 1 \le S_i, V_i, C_j \le 10^9 (1 \le i \le N, 1 \le j \le M)$

分析

很裸的贪心题。

首先显然我们把画框大小排序之后答案是不变的，且排序之后就有了单调性，方便处理。故需要对其进行排序。

之后考虑如何处理画？我们将画按照美观度为第一关键字，大小为第二关键字进行排序，这样画的美观度就有了单调性。

显然，大画框是可以放小画的，且因为之前的两次排序，我们画框的大小和美观度都有了单调性，故直接扫一遍，能放就放即可。

时间复杂度 $O(n \log n)$ ，瓶颈在于排序。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 100000 + 5;
const int HA = 998244353;

ll n , m , c[M];

struct Node{
    ll s , v;
}k[M];

bool cmp(Node a , Node b) {
    if(a.v == b.v) return a.s < b.s; 
    else return a.v < b.v;
}

#define LOCAL

int main() {
    #ifdef LOCAL
        freopen("a.in" , "r" , stdin);
        freopen("a.out" , "w" , stdout);
    #endif
    read(n) , read(m);
    rep(i , 1 , n) read(k[i].s) , read(k[i].v);   
    rep(i , 1 , m) read(c[i]);
    
    sort(c + 1 , c + 1 + m);
    sort(k + 1 , k + 1 + n , cmp);
    
    ll now = n , ans = 0;
    per(i , m , 1) {
        while(now && k[now].s > c[i]) now --;
        if(now) ans ++ , now --;
    }
    printf("%lld\n" , ans);

    return 0;
}