Неперетинаючийся шлях коня#11563
Класична головоломка полягає в тому, щоб "обійти" конем усі клітинки шахової дошки розміром 8 \times 8. Конь — це фігура, яка ходить, перестрибуючи на одну клітинку в одному напрямку і на дві клітинки в перпендикулярному напрямку. Потрібно відвідати кожну клітинку дошки рівно один раз, а потім повернутися на початкову. Існує безліч способів зробити це, а розмір дошки достатньо малий, тому таке завдання при бажанні може вирішити і людина.
Однак у Вас є комп'ютер і навички програмування! Тому ми пропонуємо більш складний варіант задачі для прямокутної дошки розміром m \times n з додатковим обмеженням: конь ніколи не повинен пересікати свій власний шлях. Якщо уявити маршрут як набір відрізків прямих, що з'єднують центри клітинок, між якими виконуються ходи, то ці відрізки повинні утворювати простий багато-кутник. Інакше кажучи, жодні два відрізки не можуть пересікатися або стикатися, за виключенням сусідніх, які мають спільну кінцеву точку.
Через це обмеження стає неможливим відвідати всі клітинки дошки. Тому тепер потрібно максимізувати кількість клітинок, які зможе відвідати конь. При цьому зберігається вимога, що маршрут повинен закінчуватися в початковій клітинці. На рисунку наведено оптимальне рішення для першого прикладу — дошки 6 \times 6.
Два цілих числа m~(1 \le m \le 8) і n~(1 \le n \le 10^{15}) — розміри прямокутної шахової дошки.
Виведіть найбільшу кількість клітинок, яке може відвідати конь під час обходу дошки m \times n, не перетинаючи свій шлях. Якщо такого шляху не існує, виведіть .
Приклад 1
Приклад 2
Приклад 3
Приклад 4