You are the proud leader of a city in Ancient Berland. There are (n^2) buildings arranged in a grid of (n) rows and (n) columns. The height of the building in row (i) and column (j) is (h_{i, j}). The city is beautiful if no two adjacent by side buildings have the same height. In other words, it must satisfy the following: There does not exist a position ((i, j)) ((1 \leq i \leq n), (1 \leq j \leq n - 1)) such that (h_{i, j} = h_{i, j + 1}). There does not exist a position ((i, j)) ((1 \leq i \leq n - 1), (1 \leq j \leq n)) such that (h_{i, j} = h_{i + 1, j}). There are (n) workers at company A, and (n) workers at company B. Each worker can be hired at most once . It costs (a_i) coins to hire worker (i) at company A. After hiring, worker (i) will: Increase the heights of all buildings in row (i) by (1). In other words, increase (h_{i, 1}, h_{i, 2}, \ldots, h_{i, n}) by (1). It costs (b_j) coins to hire worker (j) at company B. After hiring, worker (j) will: Increase the heights of all buildings in column (j) by (1). In other words, increase (h_{1, j}, h_{2, j}, \ldots, h_{n, j}) by (1). Find the minimum number of coins needed to make the city beautiful, or report that it is impossible. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 100)). The description of the test cases follows. The first line of each test case contains a single integer (n) ((2 \le n \le 1000)) — the size of the grid. The (i)-th of the next (n) lines of each test case contains (n) integers (h_{i, 1}, h_{i, 2}, \ldots, h_{i, n}) ((1 \le h_{i, j} \le 10^9)) — the heights of the buildings in row (i). The next line of each test case contains (n) integers (a_1, a_2, \ldots, a_n) ((1 \le a_i \le 10^9)) — the costs of hiring the workers at company A. The next line of