AND-шлях#11362

AND-шлях

1 секунда

256 мегабайтів

Легка

Одного разу Андрій брав участь в олімпіаді з програмування. За перше місце був дуже цінний приз — мішок цукерок. Проте, скільки б він не намагався розв'язати останню задачу, в нього нічого не виходило, саме тому він звертається по допомогу до вас.

Вам дана матриця розмірами $n \times m$ n \times m, де на перетині $i$ -того рядка та $j$ -того стовпчика знаходиться елемент $a_{i, j}$ a_{i,j}. Рядки нумеруються зверху вниз від $1$ до $n$ , а стовпчики зліва направо від $1$ до $m$ . Ліва верхня клітинка має координати $(1; 1)$ . Треба знайти максимальне значення побітового AND чисел на шляху від лівої верхньої до правої нижньої клітинки матриці, якщо можна ходити тільки у праву або нижню клітинку (якщо вони існують).

Через AND позначено побітове І. Операція побітового І між двома числами $a$ і $b$ визначається на парах відповідних бітів чисел: якщо обидва біти дорівнюють $1$ , то у відповіді біт на цій позиції дорівнює $1$ , інакше — $0$ . Наприклад, $6$ AND $3$ = $0110$ AND $0011$ = $0010$ = $2$ .

Вхідні дані

Перший рядок містить два цілі числа $n$ та $m$ ( $1 \leq n, m \leq 1 0^{3}$ 1 \le n,m \le 10^3) — кількість рядків та стовпчиків відповідно.

Наступні $n$ рядків містять $m$ цілих чисел $a_{i, j}$ a_{i,j} ( $0 \leq a_{i, j} < 2^{60}$ 0 \le a_{i,j} < 2^{60}) — значення елементів матриці.

Вихідні дані

Виведіть одне ціле число — максимальне значення AND елементів на шляху від лівої верхньої до правої нижньої клітинки матриці.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

Детальніше про побітове І: http://bit.ly/3Whf2l6

Пояснення до першого прикладу:

З лівої верхньої клітинки до правої нижньої існують два шляхи:

$(1; 1)$ , $(1; 2)$ , $(2; 2)$ — елементи на цих позиціях мають значення $7$ , $3$ та $2$ відповідно. $7$ AND $3$ AND $2$ = 2.

$(1; 1)$ , $(2; 1)$ , $(2; 2)$ — елементи на цих позиціях мають значення $7$ , $4$ та $2$ відповідно. $7$ AND $4$ AND $2$ = 0.

Пояснення до другого прикладу:

Одним з можливих шляхів є шлях з виділених червоним чисел. $15$ AND $13$ AND $14$ AND $31$ AND $31$ AND $4$ AND $12$ = 4.

Двійкова матриця з другого прикладу

Оцінювання

Рішення, які правильно працюють при $n \times m \leq 25$ n \times m \le 25 набиратимуть принаймні $15$ балів.

Рішення, які правильно працюють при $a_{i, j} \leq 32$ a_{i,j} \le 32 набиратимуть принаймні $15$ балів.