CF2096C Wonderful City

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 each test case contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 1 \le b_j \le 10^9 $ ) — the costs of hiring the workers at company B. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 1000 $ .

For each test case, output a single integer — the minimum number of coins needed, or $ -1 $ if it is impossible.

For the first test case, we can see that the city is already beautiful. Thus, the answer is $ 0 $ . For the second test case, we can hire worker $ 2 $ from company A, worker $ 4 $ from company A, and worker $ 4 $ from company B: $ 1 $ $ 2 $ $ 1 $ $ \color{red}2 $ $ \implies $ $ 1 $ $ 2 $ $ 1 $ $ \color{red}3 $ $ \color{red}3 $ $ \color{red}2 $ $ \color{red}1 $ $ \color{red}2 $ $ \color{red}4 $ $ \color{red}3 $ $ \color{red}2 $ $ \color{red}4 $ $ 1 $ $ 2 $ $ 1 $ $ \color{red}1 $ $ 1 $ $ 2 $ $ 1 $ $ \color{red}2 $ $ \color{red}1 $ $ \color{red}3 $ $ \color{red}1 $ $ \color{red}2 $ $ \color{red}2 $ $ \color{red}4 $ $ \color{red}2 $ $ \color{red}4 $ The cost of hiring the workers is $ 2 + 4 + 8 = 14 $ . This is the minimum possible cost. For the third test case, no matter what we do, it is impossible to make the city beautiful. Thus, the answer is $ -1 $ .