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:
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.
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$$$:
Additional constraint on the input: the inventory contains at least one item of each type.
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.
8sword 3 catshield 3 bearsword 2 vipershield 2 viperarmor 1 viperhelmet 2 manticorehelmet 2 viperhelmet 1 viper
14
5shield 6 bearhelmet 1 viperarmor 1 vipersword 1 vipershield 1 viper
9