You are in charge of making sure all the students have finished all their homework before they go to bed.

You ask all the teachers about the homework of each student. With your genius intellect you are quickly able to determine how much time each tasks will take each student.

You have k hours in a day, n students and m homework tasks, with each homework task containing which student it is assigned to and how long it will take for that student to complete it.

Determine the number of students who can finish their homework before they sleep (given that they can only work for at most k hours).

Input

Your first line will contain three space-separated integers n (n <= 100000), m (m <= 100000) and k (k <= 1000000000).

Then m lines will follow, each containing two space-separated integers s and h (1 <= h <= k) representing a homework task where s (1 <= s <= n) is the ID of the student and h is the number of hours that it will take for them to finish that task.

You are not guaranteed to be given the homework tasks in any particular order.

Output

You should output a single integer representing the number of students who can finish their homework before they sleep.

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

Output 1
2

Explanation 1 Student one has three homework tasks, one which takes an hour, and two which takes two hours which adds up to a total of five hours, which means they can finish before sleeping. Student two has only two homework tasks but one of length 4 hours and one of length 2 hours, meaning they cannot fit all their tasks into the five hours they have to work. Similarly, student three has one hours worth of homework tasks, meaning they can also finish. So two people can finish out of the three.