{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n 为了防止某位张姓男子AK,现特加一防AK题目。题解即为本题标题,欢迎各位尝试AC。\u003cbr\u003e\n Recently George is preparing for the Graduate Record Examinations (GRE for short). Obviously the most important thing is reciting the words. \n \u003cbr\u003eNow George is working on a word list containing N words. \n \u003cbr\u003eHe has so poor a memory that it is too hard for him to remember all of the words on the list. But he does find a way to help him to remember. He finds that if a sequence of words has a property that for all pairs of neighboring words, the previous one is a substring of the next one, then the sequence of words is easy to remember. \n \u003cbr\u003eSo he decides to eliminate some words from the word list first to make the list easier for him. Meantime, he doesn\u0027t want to miss the important words. He gives each word an importance, which is represented by an integer ranging from -1000 to 1000, then he wants to know which words to eliminate to maximize the sum of the importance of remaining words. Negative importance just means that George thought it useless and is a waste of time to recite the word. \n \u003cbr\u003eNote that although he can eliminate any number of words from the word list, he can never change the order between words. In another word, the order of words appeared on the word list is consistent with the order in the input. In addition, a word may have different meanings, so it can appear on the list more than once, and it may have different importance in each occurrence. \n \u003cbr\u003e \n \u003ccenter\u003e \n \u003cimg style\u003d\"max-width:100%;\" SRC\u003d\"CDN_BASE_URL/665d024409267f69402b0106efb6722f?v\u003d1573228434\"\u003e \n \u003c/center\u003e \n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer T(1 \u0026lt;\u003d T \u0026lt;\u003d 50), indicating the number of test cases. \n\u003cbr\u003eEach test case contains several lines. \n\u003cbr\u003eThe first line contains an integer N(1 \u0026lt;\u003d N \u0026lt;\u003d 2 * 10 \n\u003csup\u003e4\u003c/sup\u003e), indicating the number of words. \n\u003cbr\u003eThen N lines follows, each contains a string S \n\u003csub\u003ei\u003c/sub\u003e and an integer W \n\u003csub\u003ei\u003c/sub\u003e, representing the word and its importance. S \n\u003csub\u003ei\u003c/sub\u003e contains only lowercase letters. \n\u003cbr\u003eYou can assume that the total length of all words will not exceeded 3 * 10 \n\u003csup\u003e5\u003c/sup\u003e."}},{"title":"Output","value":{"format":"HTML","content":"For each test case in the input, print one line: \"Case #X: Y\", where X is the test case number (starting with 1) and Y is the largest importance of the remaining sequence of words."}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e1\n5\na 1\nab 2\nabb 3\nbaba 5\nabbab 8\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003eCase #1: 14\u003c/pre\u003e"}}]}