410055: GYM103934 C Book of the Dead's spells

The Book of the Dead is a collection of Ancient Egypt's texts that was used to cast spells which purpose was to assist a dead person's journey through the Duat and into the afterlife.

The book contains magic words, each of them with a certain level of magic power. To cast a spell, one must say a sequence of magic words in which every said word (but the first one) is such that the previous one is a proper prefix of the latter. For instance, the sequence of magic words nefer neferti nefertiti is a spell, whereas ra ramses ramesses and amun amun amunra aren't. The magic power of a spell is the sum of magic powers of each of the magic words in it.

Given the list of the Book of the Dead's magic words, answer what is the maximum power of a spell that can be cast using only the magic words in that list.

The first line has an integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$), the number of magic words.

The next $$$n$$$ lines describe a magic word with a string $$$s_i$$$ (containing only lowercase letters of the English alphabet) and a integer $$$p_i$$$ ($$$1 \leq p_i \leq 10^9$$$), which means that the magic power of the word $$$s_i$$$ is $$$p_i$$$.

It is guaranteed that the $$$n$$$ magic words are different and that the sum of their lengths is less than or equal to $$$10^6$$$.

Print a single integer: the maximum power of a spell.

7
nefer 1
amun 3
nefertari 10
neferti 2
nefertem 4
nefertiti 9
amunra 10

13