{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eNudgémon GO is a game in which players should earn as much\n experience points (\u003ci class\u003d\"itshape\"\u003eXP\u003c/i\u003e) as possible, by\n catching and evolving Nudgémon. You gain 100 XP for catching a\n Nudgémon and 500 XP for evolving a Nudgémon. Your friend has\n been playing this game a lot recently, but you believe that his\n strategy is not optimal.\u003c/p\u003e\n\n \u003cp\u003eAll Nudgémon are split into families, each of which has its\n own unique type of \u003cem\u003ecandy\u003c/em\u003e. The Nudgémon in a family are\n ranked from weakest to strongest and hence form a chain. Any\n Nudgémon that is not the strongest from its family can be\n evolved to the next ranked Nudgémon from the same family.\u003c/p\u003e\n\n \u003cp\u003eCandies are a fundamental currency in the Nudgémon\n universe:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eWhen you catch a Nudgémon you earn 3 candies, all\n associated with the Nudgémon’s family.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eWhen you irreversibly transfer a Nudgémon away from your\n possession, you earn 1 candy associated with the Nudgémon’s\n family.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eEvery evolution of a Nudgémon consumes a specific amount of\n its family’s kind of candy. Furthermore, the costs of\n evolutions along the family chain are non-decreasing, meaning\n that higher-ranked evolutions in the family will cost the same\n or more as lower ones.\u003c/p\u003e\n\n \u003cp\u003eHere is an example of possible Nudgémon evolutions:\u003c/p\u003e\n\n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/6e88939ebbd9223efd50314aeadea99c?v\u003d1715984019\" alt\u003d\"\\includegraphics[width\u003d1.0\\textwidth ]{example-fig}\" style\u003d\"width:100.00%\"\u003e\u003c/p\u003e\n\n \u003cp\u003eApart from making the developers money and nudging ’em all,\n the goal of this game is to earn as much XP as possible to\n level up the player’s character and be able to encounter\n stronger Nudgémon in the wild. As such, coinciding with the\n first goal, you can buy a \u003ci class\u003d\"itshape\"\u003eBlessed Egg\u003c/i\u003e\n with real money in the game. This item allows you to double\n your earned XP for the next 30 minutes since activation,\n i.e.\u0026nbsp;when the Egg is activated at time \u003cspan class\u003d\"tex2jax_process\"\u003e$e$\u003c/span\u003e (in seconds since the start of the\n game), for any action taken on time \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e, you will earn double XP if and\n only if \u003cspan class\u003d\"tex2jax_process\"\u003e$e \\leq t \u0026lt; e +\n 1800$\u003c/span\u003e.\u003c/p\u003e\n\n \u003cp\u003eAt the start of the game your friend received a single\n Blessed Egg. Unfortunately, he completely wasted it. You\n believe that it is better to only evolve Nudgémon while the\n Blessed Egg is active, otherwise it is a huge waste of\n resources! To prove your point to your friend, you took a log\n of all Nudgémon he caught with timestamps and decided to\n calculate the maximum amount of XP he could have had right now\n if he was strategic about when to activate his Blessed Egg and\n only evolved Nudgémon during the time it was active.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eone line containing an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$f$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq f \\leq 10^5$\u003c/span\u003e), the number\n of Nudgémon families;\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$f$\u003c/span\u003e lines\n describing a family of Nudgémon, where each line consists\n of the following elements:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003ean integer \u003cspan class\u003d\"tex2jax_process\"\u003e$s_\n i$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le s_ i\n \\leq 10^5$\u003c/span\u003e), the number of Nudgémon in this\n family;\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$s_ i-1$\u003c/span\u003e times\n the name of a Nudgémon, followed by an integer\n \u003cspan class\u003d\"tex2jax_process\"\u003e$c_ j$\u003c/span\u003e\n (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le c_ j \\leq\n 10^5$\u003c/span\u003e), the amount of candies (of appropriate\n type) consumed by evolving this Nudgémon;\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003ethe name of the strongest Nudgémon in this\n family;\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eone line containing an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq n \\leq 4 \\cdot 10^5$\u003c/span\u003e), the\n number of Nudgémon your friend caught;\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines\n containing an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$t_\n i$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq t_ i \\leq\n 10^9$\u003c/span\u003e) and a string \u003cspan class\u003d\"tex2jax_process\"\u003e$p_ i$\u003c/span\u003e, the time at which the\n Nudgémon was caught and the name of the caught\n Nudgémon.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eIt is guaranteed that there are at most \u003cspan class\u003d\"tex2jax_process\"\u003e$10^5$\u003c/span\u003e Nudgémon kinds (\u003cspan class\u003d\"tex2jax_process\"\u003e$\\sum _{i} s_ i \\leq 10^5$\u003c/span\u003e). The\n Nudgémon in each family are given in order of increasing rank,\n and thus the values of \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e\n in one family are non-decreasing. Every Nudgémon name is a\n string of between \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$20$\u003c/span\u003e lowercase letters.\n The times \u003cspan class\u003d\"tex2jax_process\"\u003e$t_ i$\u003c/span\u003e are\n non-decreasing (your friend is so quick he can catch multiple\n Nudgémon in a single second). No Nudgémon name appears more\n than once within a family or within more than one family, and\n all \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e Nudgémon that are\n caught belong to one of the families.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput the maximum amount of XP your friend could have had\n at the current time had he activated his Blessed Egg at the\n optimal time and only evolved Nudgémon during the time it was\n active.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n3 caterpillar 3 pupa 7 butterfly\n3 dove 3 pigeon 7 aaabaaajss\n3 mouse 1 electromouse 5 rat\n7\n0 electromouse\n500 electromouse\n1000 electromouse\n1500 rat\n2000 aaabaaajss\n2500 pigeon\n3000 butterfly\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5100\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1 slownudge\n2\n0 slownudge\n1800 slownudge\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e300\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}