{"problem":{"name":"Friction","description":{"content":"Mr. Takahashi has in his room an art object with $H$ rows and $W$ columns, made up of $H \\times W$ blocks. Each block has a color represented by a lowercase English letter (`a`\\-`z`). The color of the","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"codefestival_2016_qualC_d"},"statements":[{"statement_type":"Markdown","content":"Mr. Takahashi has in his room an art object with $H$ rows and $W$ columns, made up of $H \\times W$ blocks. Each block has a color represented by a lowercase English letter (`a`\\-`z`). The color of the block at the $i$\\-th row and $j$\\-th column is $c_{i,j}$.\nMr. Takahashi would like to dismantle the object, finding it a bit kitschy for his tastes. The dismantling is processed by repeating the following operation:\n\n*   Choose one of the $W$ columns and push down that column one row. The block at the bottom of that column disappears.\n\nEach time the operation is performed, a cost is incurred. Since blocks of the same color have a property to draw each other together, the cost of the operation is the number of the pairs of blocks $(p, q)$ such that:\n\n*   The block $p$ is in the selected column.\n*   The two blocks $p$ and $q$ are horizontally adjacent (before pushing down the column).\n*   The two blocks $p$ and $q$ have the same color.\n\nMr. Takahashi dismantles the object by repeating the operation $H \\times W$ times to get rid of all the blocks. Compute the minimum total cost to dismantle the object.\n\n## Constraints\n\n*   $1 ≤ H ≤ 300$\n*   $2 ≤ W ≤ 300$\n*   All characters $c_{i,j}$ are lowercase English letters (`a`\\-`z`).\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$H$ $W$\n$c_{1,1}c_{1,2}$..$c_{1,W}$\n$c_{2,1}c_{2,2}$..$c_{2,W}$\n$:$\n$c_{H,1}c_{H,2}$..$c_{H,W}$\n\n## Partial Score\n\n*   In test cases worth $300$ points, $W = 3$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"codefestival_2016_qualC_d","tags":[],"sample_group":[["2 3\nrrr\nbrg","2\n\nFor example, the total cost of $2$ can be achieved by performing the operation as follows and this is the minimum value.\n\n![image](https://atcoder.jp/img/code-festival-2016-qualc/ccb25ed6f1df9367829b68523e1deff4.png)"],["6 3\nxya\nxya\nayz\nayz\nxaz\nxaz","0\n\nThe total cost of $0$ can be achieved by first pushing down all blocks of the middle column, then all of the left column, and all of the right column."],["4 2\nay\nxa\nxy\nay","0\n\nThe total cost of $0$ can be achieved by the following operations:\n\n*   pushing down the right column one row;\n*   pushing down the left column one row;\n*   pushing down all of the right column;\n*   and pushing down all of the left column."],["5 5\naaaaa\nabbba\nababa\nabbba\naaaaa","24"],["7 10\nxxxxxxxxxx\nccccxxffff\ncxxcxxfxxx\ncxxxxxffff\ncxxcxxfxxx\nccccxxfxxx\nxxxxxxxxxx","130"]],"created_at":"2026-03-03 11:01:14"}}