CF903F Clear The Matrix

You are given a matrix $ f $ with $ 4 $ rows and $ n $ columns. Each element of the matrix is either an asterisk (\*) or a dot (.). You may perform the following operation arbitrary number of times: choose a square submatrix of $ f $ with size $ k×k $ (where $ 1

The first line contains one integer $ n $ ( $ 4

Print one integer — the minimum number of coins to replace all asterisks with dots.

In the first example you can spend $ 8 $ coins to replace the submatrix $ 3×3 $ in the top-left corner, and $ 1 $ coin to replace the $ 1×1 $ submatrix in the bottom-right corner. In the second example the best option is to replace the $ 4×4 $ submatrix containing columns $ 2–5 $ , and the $ 2×2 $ submatrix consisting of rows $ 2–3 $ and columns $ 6–7 $ . In the third example you can select submatrix $ 3×3 $ in the top-left corner and then submatrix $ 3×3 $ consisting of rows $ 2–4 $ and columns $ 2–4 $ .