MWC '15 #1 P1: Playlist Panic

View as PDF

Submit solution

Points: 3
Time limit: 2.0s
Memory limit: 256M

Problem type

aurpine likes to listen to various songs in his music playlist, especially by Young Thug. Specifically, his playlist contains N (1 \leq N \leq 1000) songs. However, being extremely busy, he does not have a lot of time to listen to music.

Each song takes a certain amount of time to listen to, specifically M_i (0 \leq M_i \leq 100) minutes and S_i (0 \leq S_i \leq 100) seconds.

If aurpine has X (0 \leq X \leq 100) minutes and Y (0 \leq Y \leq 100) seconds to listen to music today, what is the maximum number of songs he can listen to?

Input Specification

The first line contains one integer, N, specifying the number of songs in the playlist.

The next N lines each have two space separated integers, M_i and S_i specifying the time it takes to listen to the i^{th} song in minutes and seconds.

The last line of input contains two space separated integers X and Y representing the time that aurpine has to listen to his playlist. X represents the amount of time in minutes and Y representing the time in seconds.

Output Specification

The output should consist of one integer representing the maximum number of songs that can be listened to.

Sample Input

1 30
2 45
4 90
0 10
14 2
9 44

Sample Output


Explanation for Sample Output

The 1st, 2nd and 4th songs can be played in the given time.