Maximizing Brushing Problems

Little A loves solving problems and is known for his relentless problem-solving habit. He has discovered \( n \) favorite problems, each requiring a certain amount of time, and he has been assigned \( m \) homework assignments. Each homework assignment requires some time and yields a certain score. According to his teacher, a total score of at least \( k \) is needed to pass. With only \( r \) units of time remaining, Little A wants to complete a set of assignments to pass while using any leftover time to solve as many of his favorite problems as possible.

The task is to determine the maximum number of favorite problems that Little A can solve while ensuring that he achieves a passing score from his homework assignments. If it is impossible to reach a passing score with the available assignments within the given time, output -1.

inputFormat

The input is given as follows:

1. The first line contains four integers \( n \), \( m \), \( k \), and \( r \) (where \( n \) is the number of favorite problems, \( m \) is the number of homework assignments, \( k \) is the minimum score needed to pass, and \( r \) is the total available time).
2. The second line contains \( n \) integers, each representing the time required to solve one favorite problem.
3. The following \( m \) lines each contain two integers \( t \) and \( s \), representing the time required and the score obtained for a homework assignment respectively.

outputFormat

Output a single integer representing the maximum number of favorite problems Little A can solve after completing a subset of homework assignments that yields a total score of at least \( k \) within the available time \( r \). If it is impossible to reach the passing score, output -1.

sample

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

4