题意描述

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

展览有 $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

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

Output ‘s eg

2

数据范围和约定

对于所有输入数据,有 $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;
}

THE END