Description

On Animal Farm, the animals have rebelled against their human owner and have taken over the management of the farm. To ensure equality and fairness among all the animals, they have decided to create a new set of rules. However, as the new leaders, the pigs have started making changes to the rules to favor themselves.

The farm maintains a hierarchy of animals based on their species, with each animal assigned a specific influence level. This influence level, represented as a positive integer, determines the animal’s priority in decision-making. Within a group, an animal can make decisions if it has the highest influence level among the members.

The pigs have a plan to maximize their collective influence in the leadership council by selecting a specific group of animals. Given a list of animals with their species and influence levels, you are tasked to form the most influential leadership council while adhering to the following rules:

1. Only one pig species is allowed in the council to avoid power conflicts among the pigs.
2. Every council member of non-pig species should have an influence level less than the influence level of the only pig’s in the council.

Determine the maximum total influence levels of the council that can be formed under these rules.

Input Format

The first line contains an integer $n$, representing the number of animals. The next $n$ lines each contain a string species and a positive integer influence:

• species is a string representing the species of the animal, e.g., “pig”, “horse”, “cow”, etc.
• influence is an integer representing the influence level of the animal.

Output Format

Output a single integer, the maximum total influence levels of the leadership council that can be formed following the rules.

5
pig 10
horse 15
pig 5
cow 20
sheep 25

10

5
pig 10
horse 15
pig 15
cow 15
sheep 10

25

Hint

• $1 \le n \le 10^5$.
• The length of species is at most $10$.
• species consists of only English characters in lowercase.
• At least one animal’s species is pig.
• influence is at most $10^8$.