{"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\u003eZS the Coder と Chris the Baboon は Udayland に到着しました!彼らは公園を歩き、そこには\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e本の木があります。彼らはいたずらをして公園の木々を色付けすることにしました。木々は左から右に向かって整数で番号が振られています。\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003eから\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003eまでの整数で番号が振られています。\u003c/p\u003e\u003cp\u003e最初、木\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003eは色\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003eです。ZS the Coder と Chris the Baboon は\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e種類の色しか認識できません。したがって、\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003em\u003c/i\u003e\u003c/span\u003eです。ここで、\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u003d 0\u003c/span\u003eは木\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003eが\u003cspan class\u003d\"tex-font-style-it\"\u003e着色されていない\u003c/span\u003eことを意味します。\u003c/p\u003e\u003cp\u003eZS the Coder と Chris the Baboon は着色されていない木のみを着色することにしました、つまり\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u003d 0\u003c/span\u003eの木を着色します。それぞれの木を\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e種類の色の中から\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003eから\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003eまでの色で着色することができます。木\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003eを色\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003eで着色するには、ちょうど\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e, \u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003eリットルのペンキが必要です。\u003c/p\u003e\u003cp\u003e2人の友達は、木々を全て同じ色の木の連続したグループに分割して、全ての木々を分割することができる連続したグループの最小数を、\u003cspan class\u003d\"tex-font-style-it\"\u003e美しさ\u003c/span\u003eと定義します。例えば、木々の色が左から右に\u003cspan class\u003d\"tex-span\"\u003e2, 1, 1, 1, 3, 2, 2, 3, 1, 3\u003c/span\u003eのようになっている場合、着色の美しさは\u003cspan class\u003d\"tex-span\"\u003e7\u003c/span\u003eです。なぜなら、木々を\u003cspan class\u003d\"tex-span\"\u003e7\u003c/span\u003e個の連続した同じ色のグループに分割できるからです:\u003cspan class\u003d\"tex-span\"\u003e{2}, {1, 1, 1}, {3}, {2, 2}, {3}, {1}, {3}\u003c/span\u003e。\u003c/p\u003e\u003cp\u003eZS the Coder と Chris the Baboon は、着色の美しさが\u003cspan class\u003d\"tex-font-style-bf\"\u003eちょうど\u003c/span\u003e\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003eになるように着色されていない木を全て着色したいと思っています。そのために、この仕事を終えるのに必要な最小量のペンキを決定するのにあなたの助けが必要です。\u003c/p\u003e\u003cp\u003e着色済みの木々は着色することができないことに注意してください。\u003c/p\u003e"}},{"title":"入力","value":{"format":"HTML","content":"\u003cp\u003e最初の行には3つの整数、\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ek\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e ≤ 100\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003em\u003c/i\u003e ≤ 100\u003c/span\u003e)が含まれています。これは木の数、色の数、および着色の美しさです。\u003c/p\u003e\u003cp\u003e2番目の行には\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e個の整数\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003em\u003c/i\u003e\u003c/span\u003e)が含まれており、木の初期の色が示されています。\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003eは、木番号\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003eが着色されていない場合は\u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003eに等しく、そうでない場合は\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e番目の木が色\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003eであることを示します。\u003c/p\u003e\u003cp\u003eその後に\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e行が続きます。それぞれの行には\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e個の整数が含まれています。各行の\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e番目の数は、\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e, \u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e, \u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e)を示します。これは木\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003eを色\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003eで着色するために友達が必要とするリットル数です。\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e, \u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003eは、最初に着色された木についても指定されていますが、そのような木は着色することはできません。\u003c/p\u003e"}},{"title":"出力","value":{"format":"HTML","content":"\u003cp\u003e1つの整数を出力し、木を着色するために必要な最小量のペンキを示します。着色の美しさが\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003eである有効な木の着色がない場合は、\u003cspan class\u003d\"tex-span\"\u003e - 1\u003c/span\u003eを出力してください。\u003c/p\u003e"}},{"title":"サンプル1","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 2 2\n0 0 0\n1 2\n3 4\n5 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"サンプル2","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 2 2\n2 1 2\n1 3\n2 4\n3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"サンプル3","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 2 2\n2 0 0\n1 3\n2 4\n3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"サンプル4","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 2 3\n2 1 2\n1 3\n2 4\n3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003eサンプルケース1では、木々を色\u003cspan class\u003d\"tex-span\"\u003e2, 1, 1\u003c/span\u003eで着色することで使用されるペンキの量が最小化され、\u003cspan class\u003d\"tex-span\"\u003e2 + 3 + 5 \u003d 10\u003c/span\u003eになります。ここで、\u003cspan class\u003d\"tex-span\"\u003e1, 1, 1\u003c/span\u003eは、そのような着色の美しさが\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003eに等しいため、有効ではありません(\u003cspan class\u003d\"tex-span\"\u003e{1, 1, 1}\u003c/span\u003eは同じ色の木々を1つのグループにまとめる方法です)。\u003c/p\u003e\u003cp\u003eサンプルケース2では、全ての木が着色されていますが、着色の美しさは\u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003eです。そのため、有効な着色がないため、答えは\u003cspan class\u003d\"tex-span\"\u003e - 1\u003c/span\u003eです。\u003c/p\u003e\u003cp\u003e最後のサンプルケースでは、全ての木が着色され、着色の美しさが\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003eに一致するため、ペンキは使用されず、答えは\u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003eになります。\u003c/p\u003e"}}]}