{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAndi is getting married! He and his partner plan to have $$$N$$$ children. To avoid any hassle in the future, Andi wants to decide all their children\u0027s name in advance. Specifically, he wants each child to have a name which is lexicographically \u003cspan class\u003d\"tex-font-style-bf\"\u003elarger\u003c/span\u003e than any of his/her older siblings. Of course, his partner also agrees with this idea. String $$$A$$$ is lexicographically larger than string $$$B$$$ if and only if $$$B$$$ is a prefix of $$$A$$$ or there exists an index $$$i$$$ where $$$A_i \u0026gt; B_i$$$ and $$$A_j \u003d B_j$$$ for all $$$j \u0026lt; i$$$. Note that a proper name can be as short as one character, but it \u003cspan class\u003d\"tex-font-style-bf\"\u003ecannot\u003c/span\u003e be an empty string.\u003c/p\u003e\u003cp\u003eLife is good for Andi, until one day he told his soon-to-be-grandmother-in-law (i.e. his partner\u0027s grandma) about this marriage plan. After learning that Andi plans to have $$$N$$$ children with her granddaughter, she gave him $$$N$$$ names to be used. Moreover, the $$$i^{th}$$$ name can only be used for the $$$i^{th}$$$ child.\u003c/p\u003e\u003cp\u003eAfter going through a long debate with her grandma, Andi came into an agreement: The $$$i^{th}$$$ child\u0027s name should be a subsequence of the $$$i^{th}$$$ name her grandma gave. A string $$$A$$$ is a subsequence of string $$$B$$$ if $$$A$$$ can be obtained by deleting zero or more characters from $$$B$$$ without changing the remaining characters\u0027 order, e.g., \u003cspan class\u003d\"tex-font-style-tt\"\u003eABC\u003c/span\u003e is a subsequence of \u003cspan class\u003d\"tex-font-style-tt\"\u003eD\u003cspan class\u003d\"tex-font-style-underline\"\u003eA\u003c/span\u003eE\u003cspan class\u003d\"tex-font-style-underline\"\u003eBC\u003c/span\u003eCB\u003c/span\u003e, but \u003cspan class\u003d\"tex-font-style-tt\"\u003eEFG\u003c/span\u003e is not a subsequence of \u003cspan class\u003d\"tex-font-style-tt\"\u003eFABEGC\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eEven though Andi dislikes the given list of names, he still wants to impress his partner by showing that he can satisfy both her grandma\u0027s wish and his own desire (i.e. each child\u0027s name is lexicographically larger than any of his/her older siblings). However, Andi wonders, what is the maximum possible total length of their children names?\u003c/p\u003e\u003cp\u003eFor example, let $$$N \u003d 3$$$, and the names given by his partner\u0027s grandma are $$$($$$\u003cspan class\u003d\"tex-font-style-tt\"\u003eKARIM\u003c/span\u003e$$$,$$$ \u003cspan class\u003d\"tex-font-style-tt\"\u003ePARBUDI\u003c/span\u003e$$$,$$$ \u003cspan class\u003d\"tex-font-style-tt\"\u003eCHANDRA\u003c/span\u003e$$$)$$$. Here are several example set of names which satisfies Andi\u0027s desire: \u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$[\\texttt{AR}, \\texttt{BI}, \\texttt{CRA}]$$$ with a total length of $$$2 + 2 + 3 \u003d 7$$$. \u003c/li\u003e\u003cli\u003e $$$[\\texttt{ARI}, \\texttt{BUDI}, \\texttt{CHANDRA}]$$$ with a total length of $$$3 + 4 + 7 \u003d 14$$$. \u003c/li\u003e\u003cli\u003e $$$[\\texttt{ARIM}, \\texttt{ARUDI}, \\texttt{CHANDRA}]$$$ with a total length of $$$4 + 5 + 7 \u003d 16$$$. \u003c/li\u003e\u003cli\u003e $$$[\\texttt{AIM}, \\texttt{ARBUDI}, \\texttt{CHANDRA}]$$$ with a total length of $$$3 + 6 + 7 \u003d 16$$$. \u003c/li\u003e\u003cli\u003e $$$\\cdots$$$ \u003c/li\u003e\u003c/ul\u003e Among all sets of names which satisfy Andi\u0027s desire in this example, the maximum total length is $$$16$$$. Note that there might be cases where valid set of names cannot be obtained. In such case, you should output \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e. For example, let $$$N \u003d 2$$$ and the names given by his partner\u0027s grandma are $$$($$$\u003cspan class\u003d\"tex-font-style-tt\"\u003eZORO\u003c/span\u003e$$$,$$$ \u003cspan class\u003d\"tex-font-style-tt\"\u003eANDI\u003c/span\u003e$$$)$$$. In this example, all subsequences of the $$$2^{nd}$$$ name are lexicographically smaller than all subsequences of the $$$1^{st}$$$ name, thus, no possible valid set of names can be obtained."}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eInput begins with a line containing an integer $$$N$$$ ($$$1 \\le N \\le 15$$$) representing the number of children. The next $$$N$$$ lines, each contains a string $$$S_i$$$ ($$$1 \\le |S_i| \\le 15$$$) representing the $$$i^{th}$$$ name given by Andi\u0027s soon-to-be-grandmother-in-law. $$$S_i$$$ contains only uppercase alphabets ($$$S_{ij} \\in \\{A-Z\\}$$$).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput contains an integer in a line representing the maximum possible total length of their children names, or \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e if no possible valid set of names can be obtained.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\nKARIM\nPARBUDI\nCHANDRA\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e16\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e2\nZORO\nANDI\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e7\nHAVE\nFUN\nIN\nICPC\nJAKARTA\nTWENTY\nEIGHTEEN\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e25\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eExplanation for the sample input/output #3\u003c/span\u003e\u003c/p\u003e\u003cp\u003eOne possible solution is $$$[\\texttt{AVE}, \\texttt{FUN}, \\texttt{IN}, \\texttt{IPC}, \\texttt{JAKARTA}, \\texttt{NTY}, \\texttt{TEEN}]$$$ with a total length of $$$3 + 3 + 2 + 3 + 7 + 3 + 4 \u003d 25$$$.\u003c/p\u003e"}}]}