Рассмотрим граф на сетке, состоящей из $$$n$$$ строк и $$$n$$$ столбцов. Пусть ячейка в строке $$$x$$$ и столбце $$$y$$$ будет обозначена как $$$(x,y)$$$. Существует направленное ребро из $$$(x,y)$$$ в $$$(x+1,y)$$$ с неотрицательным целым значением $$$d_{x,y}$$$ для всех $$$1\le x < n, 1\le y \le n$$$, а также существует направленное ребро из $$$(x,y)$$$ в $$$(x,y+1)$$$ с неотрицательным целым значением $$$r_{x,y}$$$, для всех $$$1\le x \le n, 1\le y < n$$$.
Изначально вы находитесь в точке $$$(1,1)$$$ с пустым множеством $$$S$$$. Вам нужно пройтись по ребрам и в конце концов достичь $$$(n,n)$$$. Каждый раз, когда вы проходите ребро, его значение будет добавляться в $$$S$$$. Найдите максимальный MEX$$$^{\text{∗}}$$$ множества $$$S$$$, который можно получить, достигнув точки $$$(n,n)$$$.
$$$^{\text{∗}}$$$Минимальное исключенное число (MEX) массива — это наименьшее неотрицательное целое число, которое не принадлежит массиву. Например:
- MEX массива $$$[2,2,1]$$$ равен $$$0$$$, потому что $$$0$$$ не принадлежит массиву.
- MEX массива $$$[3,1,0,1]$$$ равен $$$2$$$, потому что $$$0$$$ и $$$1$$$ принадлежат массиву, а $$$2$$$ — нет.
- MEX массива $$$[0,3,1,2]$$$ равен $$$4$$$, потому что $$$0, 1, 2$$$ и $$$3$$$ принадлежат массиву, а $$$4$$$ — нет.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\le n\le20$$$) — количество строк и столбцов.
Каждая из следующих $$$n-1$$$ строк содержит $$$n$$$ целых чисел, разделенных пробелами — матрица $$$d$$$ ($$$0\le d_{x,y}\le 2n-2$$$).
Каждая из следующих $$$n$$$ строк содержит $$$n-1$$$ целых чисел, разделенных пробелами — матрица $$$r$$$ ($$$0\le r_{x,y}\le 2n-2$$$).
Гарантируется, что сумма всех $$$n^3$$$ не превосходит $$$8000$$$.
Для каждого набора входных данных выведите одно целое число — максимальное значение MEX для $$$S$$$ при достижении $$$(n,n)$$$.
231 0 20 1 32 10 33 031 2 00 1 22 01 20 1
3 2
11016 7 3 15 9 17 1 15 9 04 3 1 12 13 10 10 14 6 123 1 3 9 5 16 0 12 7 1211 4 8 7 13 7 15 13 9 22 3 9 9 4 12 17 7 10 1510 6 15 17 13 6 15 9 4 913 3 3 14 1 2 10 10 12 168 2 9 13 18 7 1 6 2 615 12 2 6 0 0 13 3 7 177 3 17 17 10 15 12 14 154 3 3 17 3 13 11 16 616 17 7 7 12 5 2 4 1018 9 9 3 5 9 1 16 71 0 4 2 10 10 12 2 14 14 15 16 15 5 8 4 187 18 10 11 2 0 14 8 182 17 6 0 9 6 13 5 115 15 7 11 6 3 17 14 51 3 16 16 13 1 0 13 11
14
В первом наборе входных данных граф решетки и один из оптимальных путей выглядят следующим образом:
Во втором наборе входных данных граф сетки и один из оптимальных путей выглядят следующим образом:
