"The Eagle's Nest" is an action adventure game. The basic idea of the game is to beat up the good guys, create public nuisance, gather money through different illegal activities and gradually become a successful gangster. But being a gangster is not so simple, not in this game, at least.

The game has a non-linear storyline which allows the players to choose from multiple alternate missions. However, there is a catch. A player can only play the missions that are harder than all the missions that he/she has completed. And once a mission is successfully completed it is no longer available for the current player. The only exception to this rule is the first mission and the final mission, which are never removed and does not even appear in the list of missions. As you might have guessed, the first mission is the easiest, and the final mission is the hardest. It is pretty obvious that one gets to complete the game without playing many missions. That's why, the authors of the game has provided some goodies to the player who would be able to complete the maximum number of missions. And trust me; the goodies are worth playing for. You'd get more health, more ammo, and more good guys to beat up!

For the hardcore gamers, there is some more exciting news. Let k be the maximum number of missions that can be completed when one plays the game for the first time. If one can play the game multiple times (starting at the first mission and finishing with the final mission) so that exactly k number of missions is completed every time and one completes the maximum number of missions possible under the given constraints, then the player would be given infinite ammo and invincibility. And that's not all; all the missions would be unlocked for the player. That means infinite ammo, infinite health and infinite amount of good guys left at your mercy.

Your task is plain and simple. You are to help a hardcore gamer by giving out the maximum number of missions that can be completed under the given constraints. Please remember, the order of the missions is important, as they are based on a storyline.

Input

The first line contains an integer n (1 < n ≤ 100). Each of the next n lines will give you the name of the mission and the difficulty level. The name of the mission will be a string of at most 20 characters, and the difficulty level would be a positive integer. You can assume that the names of the missions are case sensitive and they would be composed of alpha numeric characters and underscore only. The difficulty level would be at most 108. In a test case no mission name would be duplicated.

Output

Print the maximum number of missions that can be completed under the given constraints. This number of missions excludes the first and the final mission.