{"raw_statement":[{"iden":"problem statement","content":"You are given two length-$N$ sequences of positive integers: $X=(X_1,X_2,\\dots,X_N)$ and $Y=(Y_1,Y_2,\\dots,Y_N)$.\nAdditionally, you are given $M$ length-$N$ sequences of positive integers. The $i$\\-th sequence is $A_i = (A_{i,1},A_{i,2},\\dots,A_{i,N})$.\nFor each $i = 1,2,\\dots,M$, you must perform one of the following operations. You can independently choose which operation to perform for each $i$.\n\n*   Replace $X_j$ with $\\max(X_j,A_{i,j})$ for all integers $j$ such that $1 \\le j \\le N$.\n*   Replace $Y_j$ with $\\max(Y_j,A_{i,j})$ for all integers $j$ such that $1 \\le j \\le N$.\n\nFind the minimum possible value of $\\sum_{j=1}^{N} (X_j + Y_j)$ after all operations."},{"iden":"constraints","content":"*   $1 \\le N \\le 10$\n*   $1 \\le M \\le 500$\n*   $1 \\le X_j, Y_j, A_{i,j} \\le 500$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$X_1$ $X_2$ $\\dots$ $X_N$\n$Y_1$ $Y_2$ $\\dots$ $Y_N$\n$A_{1,1}$ $A_{1,2}$ $\\dots$ $A_{1,N}$\n$A_{2,1}$ $A_{2,2}$ $\\dots$ $A_{2,N}$\n$\\vdots$\n$A_{M,1}$ $A_{M,2}$ $\\dots$ $A_{M,N}$"},{"iden":"sample input 1","content":"3 2\n4 4 2\n3 1 5\n2 5 2\n1 2 4"},{"iden":"sample output 1","content":"21\n\nOne optimal sequence of operations is as follows:\n\n*   Replace $X_j$ with $\\max(X_j,A_{1,j})$, making $X = (4,5,2)$.\n*   Replace $Y_j$ with $\\max(Y_j,A_{2,j})$, making $Y = (3,2,5)$.\n\nThis sequence of operations achieves $\\sum_{j=1}^{N} (X_j + Y_j) = 21$."},{"iden":"sample input 2","content":"3 5\n4 13 10\n14 9 4\n4 6 4\n13 18 16\n8 13 5\n7 18 17\n20 20 14"},{"iden":"sample output 2","content":"84"},{"iden":"sample input 3","content":"5 12\n330 68 248 387 491\n295 366 376 262 192\n280 121 17 168 455\n288 179 210 378 490\n150 275 165 264 287\n66 331 207 282 367\n303 215 456 214 18\n227 326 103 443 427\n395 57 107 350 227\n318 231 146 2 116\n57 325 124 383 260\n147 319 23 177 445\n254 198 32 85 56\n68 177 356 41 471"},{"iden":"sample output 3","content":"3595"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}