Description

There are $n$ people who come to a restaurant to order dishes. The restaurant has $m$ dishes in total, and each dish has two attributes: tastiness and price. These $n$ people come once every week, and each time each person will order at most one dish or none. Among these $n$ people, $p$ people are picky; they can only accept dishes with tastiness greater than or equal to a certain value. Another $q$ people are poor; they can only order dishes with price less than or equal to a certain value. Now please compute: what is the minimum number of weeks they need to come so that it is possible to have ordered all dishes at least once?

Input Format

• Line $1$: four positive integers $n, m, p, q$.
• Lines $2 \sim m+1$: each line contains two numbers, the tastiness and the price of a dish.
• Line $m+2$: $p$ numbers, the lower bounds of acceptable tastiness for each of the $p$ picky people.
• Line $m+3$: $q$ numbers, the upper bounds of acceptable price for each of the $q$ poor people.

Output Format

Output a single number: the minimum number of weeks needed. If it is impossible to have all dishes ordered at least once no matter how many weeks they come, output $-1$.

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

3

Hint

Constraints and Conventions:

• For $20\%$ of the testdata, $m \le 20$.
• For $40\%$ of the testdata, $m \le 2000$.
• For $100\%$ of the testdata, $p+q \le n \le 50000$, $m \le 200000$.

Translated by ChatGPT 5