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