点菜
题目描述
有 $n$ 个人到一家餐馆点菜。这家餐馆总共有 $m$ 道菜,每一道菜都有两个属性——美味度和价格。这 $n$ 个人每周都会来一次,每次只会点一道菜或不点。在这 $n$ 个人中,有 $p$ 个人比较挑剔,他们只能接受美味度大于等于一定值的菜;有 $q$ 个人比较贫穷,他们只能点价格小于等于一定值的菜。现在请你计算:这些人至少要来几周,才可能能把餐馆的所有的菜都点过一遍?
输入输出格式
输入格式
第 $1$ 行,四个正整数 $n,m,p,q$。
第 $2 \sim m+1$ 行,每行两个数,表示菜的美味度和价格。
第 $m+2$ 行 $p$ 个数,表示 $p$ 个挑剔的人分别能接受的菜的美味度的下限。
第 $m+3$ 行 $q$ 个数,表示 $q$ 个贫穷的人分别能点的菜的价格的上限。
输出格式
一行一个数,即这些人最少要来的周数。若不论这些人来几周都不可能把菜点过一遍,输出 $-1$。
输入输出样例
输入样例 #1
2 3 1 1
5 2
5 3
6 4
5
1
输出样例 #1
3
说明
### 数据范围及约定
- 对于 $20\%$ 的数据,$m \le 20$;
- 对于 $40\%$ 的数据,$m \le 2000$;
- 对于 $100\%$ 的数据,$p+q \le n \le 50000,m \le 200000$。