{"problem":{"name":"Strongest Takahashi","description":{"content":"There is a $N \\times N$ grid, with blocks on some squares.   The grid is described by $N$ strings $S_1,S_2,\\dots,S_N$, as follows. *   If the $j$\\-th character of $S_i$ is `#`, there is a block on th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc233_g"},"statements":[{"statement_type":"Markdown","content":"There is a $N \\times N$ grid, with blocks on some squares.  \nThe grid is described by $N$ strings $S_1,S_2,\\dots,S_N$, as follows.\n\n*   If the $j$\\-th character of $S_i$ is `#`, there is a block on the square at the $i$\\-th row from the top and $j$\\-th column from the left.\n*   If the $j$\\-th character of $S_i$ is `.`, there is not a block on the square at the $i$\\-th row from the top and $j$\\-th column from the left.\n\nTakahashi can do the operation below zero or more times.\n\n*   First, choose an integer $D$ between $1$ and $N$ (inclusive), and a $D \\times D$ subsquare within the grid.\n*   Then, consume $D$ stamina points to destroy all blocks within the subsquare.\n\nFind the minimum number of stamina points needed to destroy all the blocks.\n\n## Constraints\n\n*   $N$ is an integer.\n*   $1 \\le N \\le 50$\n*   $S_i$ consists of `#` and `.`.\n*   $|S_i|=N$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc233_g","tags":[],"sample_group":[["5\n##...\n.##..\n#.#..\n.....\n....#","4\n\nBy choosing the subsquares below, Takahashi will consume $4$ stamina points, which is optimal.\n\n*   The $3 \\times 3$ subsquare whose top-left square is at the $1$\\-st row from the top and $1$\\-st column from the left.\n*   The $1 \\times 1$ subsquare whose top-left square is at the $5$\\-th row from the top and $5$\\-th column from the left."],["3\n...\n...\n...","0\n\nThere may be no block on the grid."],["21\n.....................\n.....................\n...#.#...............\n....#.............#..\n...#.#...........#.#.\n..................#..\n.....................\n.....................\n.....................\n..........#.....#....\n......#..###.........\n........#####..#.....\n.......#######.......\n.....#..#####........\n.......#######.......\n......#########......\n.......#######..#....\n......#########......\n..#..###########.....\n.........###.........\n.........###.........","19"]],"created_at":"2026-03-03 11:01:14"}}