{"raw_statement":[{"iden":"problem statement","content":"We have a grid with $H$ rows and $W$ columns. Each square is painted either white or black. For each integer pair $(i, j)$ such that $1 \\leq i \\leq H$ and $1 \\leq j \\leq W$, the color of the square at the $i$\\-th row from the top and $j$\\-th column from the left (we simply denote this square by Square $(i, j)$) is represented by $A_{i, j}$. Square $(i, j)$ is white if $A_{i, j} = 0$, and black if $A_{i, j} = 1$.\nYou may perform the following operations any number of (possibly $0$) times in any order:\n\n*   Choose an integer $i$ such that $1 \\leq i \\leq H$, pay $R_i$ yen (the currency in Japan), and invert the color of each square in the $i$\\-th row from the top in the grid. (White squares are painted black, and black squares are painted white.)\n*   Choose an integer $j$ such that $1 \\leq j \\leq W$, pay $C_j$ yen, and invert the color of each square in the $j$\\-th column from the left in the grid.\n\nPrint the minimum total cost to satisfy the following condition:\n\n*   There exists a path from Square $(1, 1)$ to Square $(H, W)$ that can be obtained by repeatedly moving down or to the right, such that all squares in the path (including Square $(1, 1)$ and Square $(H, W)$) have the same color.\n\nWe can prove that it is always possible to satisfy the condition in a finite number of operations under the Constraints of this problem."},{"iden":"constraints","content":"*   $2 \\leq H, W \\leq 2000$\n*   $1 \\leq R_i \\leq 10^9$\n*   $1 \\leq C_j \\leq 10^9$\n*   $A_{i, j} \\in \\lbrace 0, 1\\rbrace$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$H$ $W$\n$R_1$ $R_2$ $\\ldots$ $R_H$\n$C_1$ $C_2$ $\\ldots$ $C_W$\n$A_{1, 1}A_{1, 2}\\ldots A_{1, W}$\n$A_{2, 1}A_{2, 2}\\ldots A_{2, W}$\n$\\vdots$\n$A_{H, 1}A_{H, 2}\\ldots A_{H, W}$"},{"iden":"sample input 1","content":"3 4\n4 3 5\n2 6 7 4\n0100\n1011\n1010"},{"iden":"sample output 1","content":"9\n\nWe denote a white square by `0` and a black square by `1`. On the initial grid, you can pay $R_2 = 3$ yen to invert the color of each square in the $2$\\-nd row from the top to make the grid:\n\n0100\n0100\n1010\n\nThen, you can pay $C_2 = 6$ yen to invert the color of each square in the $2$\\-nd row from the left to make the grid:\n\n0000\n0000\n1110\n\nNow, there exists a path from Square $(1, 1)$ to Square $(3, 4)$ such that all squares in the path have the same color (such as the path $(1, 1) \\rightarrow (2, 1) \\rightarrow (2, 2) \\rightarrow (2, 3) \\rightarrow (2, 4) \\rightarrow (3, 4)$). The total cost paid is $3+6 = 9$ yen, which is the minimum possible."},{"iden":"sample input 2","content":"15 20\n29 27 79 27 30 4 93 89 44 88 70 75 96 3 78\n39 97 12 53 62 32 38 84 49 93 53 26 13 25 2 76 32 42 34 18\n01011100110000001111\n10101111100010011000\n11011000011010001010\n00010100011111010100\n11111001101010001011\n01111001100101011100\n10010000001110101110\n01001011100100101000\n11001000100101011000\n01110000111011100101\n00111110111110011111\n10101111111011101101\n11000011000111111001\n00011101011110001101\n01010000000001000000"},{"iden":"sample output 2","content":"125"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}