I. Character Pumping
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Monocarp wants to equip his RPG character for a battle. He has to choose a set of equipment consisting of a sword, a shield, a piece of armor, and a helmet. The inventory contains $$$n$$$ items. For each item, the following information is known:

  • the type of an item (sword/shield/armor/helmet);
  • the bonus to the character's strength when using this item of equipment;
  • the combat school for which this item is the most suitable. Any number of items of any type may belong to the same combat school. For example, two different swords can belong to the same school.

Monocarp needs to choose a set of exactly $$$4$$$ items, one of each type, with the maximum bonus. The set bonus is the sum of the bonuses of the equipment items it consists of. The chosen items in the set do not have to be from the same school. However, this is desirable — if all $$$4$$$ items are chosen from the same school, the set bonus is doubled.

Help Monocarp to select a sword, a shield, a piece of armor, and a helmet with the maximum set bonus.

Input

The first line contains one integer $$$n$$$ ($$$4 \le n \le 10^5$$$) — the number of items in the inventory.

Then $$$n$$$ lines follow, the $$$i$$$-th of them describes the $$$i$$$-th item as follows: it contains a string $$$t_i$$$, an integer $$$b_i$$$, and a string $$$s_i$$$:

  • $$$t_i$$$ is the item type, so it is one of the four possible strings: sword, shield, armor, or helmet;
  • $$$b_i$$$ is the strength bonus provided by the item ($$$1 \le b_i \le 10^6$$$);
  • $$$s_i$$$ is the combat school of the item ($$$1 \le |s_i| \le 10$$$, $$$s_i$$$ consists of lowercase Latin letters only).

Additional constraint on the input: the inventory contains at least one item of each type.

Output

Print one integer — the maximum set bonus Monocarp can get from an equipment set consisting of one sword, one shield, one piece of armor, and one helmet.

Examples
Input
8
sword 3 cat
shield 3 bear
sword 2 viper
shield 2 viper
armor 1 viper
helmet 2 manticore
helmet 2 viper
helmet 1 viper
Output
14
Input
5
shield 6 bear
helmet 1 viper
armor 1 viper
sword 1 viper
shield 1 viper
Output
9