Дана матрица a размера n * n из целых чисел.
Предположим, что строки матрицы пронумерованы сверху вниз от 1 к n, а столбцы слева направо от 1 к n. Пусть a[i,j]
- число на пересечении i - ой строки и j - го столбца.
Вы начинаете путь в клетке (1, 1) и можете двигаться только вниз и вправо. Путь нужно закончить в клетке (n, n). Пусть b[1]
, b[2]
, . . ., b[2n−1]
- целые числа, записанные в клетках, которые Вы посетили.
Цена пути равна b[1]
⊕ b[2]
⊕ . . . ⊕ b[2n−1]
.
Найдите путь от (1, 1) до (n, n) с минимальной ценой.
Первая строка содержит одно целое число n (2 ≤ n ≤ 20) - размер матрицы.
Каждая из следующих n строк содержит n целых чисел a[i1]
, a[i2]
, . . . , a[in]
(1 ≤ a[ij]
≤ 10^9
).
Выведите одно целое число - минимально возможную цену пути.
Выражение x ⊕ y означает применение побитовой операции XOR к числам x та y. Данная операция существует во всех современных языках программирования, например, в языках С++ и Java она обозначена как «ˆ», а в Pascal как «xor».