Minimum Weeks to Order All Dishes

You are given a restaurant scenario where there are \(n\) people and \(m\) dishes. Each dish has two attributes: its tastiness and its price. Every week, each of the \(n\) people visits the restaurant and can order at most one dish (or skip ordering). Among these people, there are:

• \(p\) picky people who will only order a dish if its tastiness is at least \(T\) (i.e. \(\text{tastiness} \ge T\)).
• \(q\) frugal people who will only order a dish if its price is at most \(L\) (i.e. \(\text{price} \le L\)).
• The remaining \(n-p-q\) people have no restrictions and can order any dish.

The restaurant has \(m\) dishes, where the \(i\)th dish is characterized by its tastiness and price. A dish can be ordered by a person only if it satisfies that person’s criteria. Note that a dish might be orderable by more than one category of person. For convenience, we can classify the dishes into four types:

• A: Dishes that only normal people can order (i.e. tastiness \( L\)).
• B: Dishes that picky people (and normal people) can order (i.e. tastiness \(\ge T\) and price \(> L\)).
• C: Dishes that frugal people (and normal people) can order (i.e. tastiness \(< T\) and price \(\le L\)).
• D: Dishes that can be ordered by anyone (i.e. tastiness \(\ge T\) and price \(\le L\)).

Your task is to determine the minimum number of weeks required so that it is possible to have every one of the \(m\) dishes ordered at least once. In each week, every person can choose at most one dish (subject to the ordering restrictions), and different people in the same week must order different dishes.

---

Input Format

The first line contains six integers \(n, m, p, q, T, L\) separated by spaces.

The following \(m\) lines each contain two integers representing the tastiness and price of a dish.

---

Output Format

Output a single integer representing the minimum number of weeks needed so that all dishes can be ordered at least once by some arrangement of orders.

---

Note: It is guaranteed that the values are such that a valid schedule exists for some number of weeks.

inputFormat

Input begins with a line containing six integers \(n, m, p, q, T, L\), where \(n\) is the total number of people, \(m\) is the number of dishes, \(p\) is the number of picky people, \(q\) is the number of frugal people, \(T\) is the tastiness threshold for picky people, and \(L\) is the price threshold for frugal people.

Then follow \(m\) lines, each containing two integers \(a_i\) and \(b_i\) representing the tastiness and price of the \(i\)th dish.

outputFormat

Output a single integer: the minimum number of weeks required so that all \(m\) dishes can be ordered at least once.

sample

5 4 1 1 7 5
6 6
8 6
6 4
8 4

1