Одного разу Андрій брав участь в олімпіаді з програмування. За перше місце був дуже цінний приз — мішок з цукерками. Проте, скільки б він не намагався розв'язувати останню задачу, в нього нічого не виходило, саме тому він звертається по допомогу до Вас.
Вам дана матриця розмірами n×m, де на перетині i-того рядка та j-того стовпчика знаходиться елемент ai,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≤n,m≤103) — кількість рядків та стовпчиків відповідно.
Наступні n рядків містять m цілих чисел ai,j (0≤ai,j<260) — значення елементів матриці.
Виведіть одне ціле число — максимальне значення AND
елементів на шляху від лівої верхньої до правої нижньої клітинки матриці.
Детальніше про побітове І: 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×m≤25 набиратимуть принаймні 15 балів.
Рішення, які правильно працюють при ai,j≤32 набиратимуть принаймні 15 балів.