Maximizing Fulfilled Wishes

Luogu's team system is powerful: a school can build its own OJ and conduct training programs at zero cost. In order to encourage OIers to recommend Luogu to their coaches, Luogu has introduced a mechanism: if an OIer successfully uses the platform (where "successful use" means that his team satisfies
\(\text{Number of members} \geq 20\), uploads \(\text{Number of private problems} \geq 10\), assigns at least one homework, and successfully holds one public contest), then the recommendation will cost a certain amount of time and money from kkksc03 in order to fulfill the recommender's wish.

Since kkksc03's time and money are limited, he cannot satisfy everyone’s wish. Given a list of wishes where each wish requires a certain amount of time and money, determine the maximum number of wishes that can be fulfilled under the resource constraints.

Note: Each wish is independent and can only be fulfilled once. The problem can be modeled as a 0/1 knapsack problem with two constraints.

The constraints can be summarized by the following inequality for each chosen wish \(i\):

[ \sum_{i \in S} t_i \leq T \quad \text{and} \quad \sum_{i \in S} m_i \leq M, ]

where \(t_i\) and \(m_i\) are the time and money required by wish \(i\), and \(T\) and \(M\) are the total available time and money, respectively.

inputFormat

The first line contains three integers \(n\), \(T\), and \(M\) (where \(n\) is the number of wishes, \(T\) is the total available time, and \(M\) is the total available money).

Each of the next \(n\) lines contains two integers: \(t_i\) and \(m_i\), representing the required time and money for the \(i\)-th wish.

It is guaranteed that \(n \geq 1\) and there are at least 3 test cases provided.

outputFormat

Output one integer: the maximum number of wishes that can be fulfilled without exceeding the total available time and money.

sample

3 10 10
5 5
6 6
4 4

2