Рассмотрим граф на сетке, состоящей из \(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)\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное значение MEX для \(S\) при достижении \((n,n)\).
Примечание
В первом наборе входных данных граф решетки и один из оптимальных путей выглядят следующим образом:
Во втором наборе входных данных граф сетки и один из оптимальных путей выглядят следующим образом:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3
1 0 2
0 1 3
2 1
0 3
3 0
3
1 2 0
0 1 2
2 0
1 2
0 1
|
3
2
|
|
2
|
1
10
16 7 3 15 9 17 1 15 9 0
4 3 1 12 13 10 10 14 6 12
3 1 3 9 5 16 0 12 7 12
11 4 8 7 13 7 15 13 9 2
2 3 9 9 4 12 17 7 10 15
10 6 15 17 13 6 15 9 4 9
13 3 3 14 1 2 10 10 12 16
8 2 9 13 18 7 1 6 2 6
15 12 2 6 0 0 13 3 7 17
7 3 17 17 10 15 12 14 15
4 3 3 17 3 13 11 16 6
16 17 7 7 12 5 2 4 10
18 9 9 3 5 9 1 16 7
1 0 4 2 10 10 12 2 1
4 14 15 16 15 5 8 4 18
7 18 10 11 2 0 14 8 18
2 17 6 0 9 6 13 5 11
5 15 7 11 6 3 17 14 5
1 3 16 16 13 1 0 13 11
|
14
|