Контрольна точка

Ви берете участь у перегонах на двовимірній ґратці, починаючи з початку координат $(0,0)$ та рухаючись до фінішу (M, N), де $M$ та $N$ — додатні цілі числа, причому 0 < M \leq N. По дорозі знаходиться проміжний контрольний пункт, який не збігається ні з початком, ні з фінішем, і розташований у точці $(m,n)$, де 0 \leq m \leq M і 0 \leq n \leq N. Ви повинні пройти через контрольний пункт перед досягненням фінішу. Довжина найкоротшого шляху до фінішу становить T = M + N.

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

Хоча існує багато способів дістатися до фінішу, проходячи через контрольний пункт, здається, що перегони надто прості, оскільки завжди легко знайти найкоротший маршрут. Щоб зробити перегони цікавішими, правила змінено. Замість того, щоб завжди рухатись до одного й того ж фінішу (M, N), учасники можуть обирати координати фінішу $(x,y)$ та контрольного пункту так, щоб існувало рівно $S$ різних найкоротших шляхів від початку до фінішу через контрольний пункт.

Наприклад, для S = 4 розглянемо два можливих розташування фінішу та контрольного пункту:

- Розташуємо контрольний пункт у $(1,3)$, а фініш — у $(2,3)$. Від початку до контрольного пункту є $4$ шляхи. Від контрольного пункту до фінішу існує лише $1$ найкоротший шлях. Таким чином, є $4$ різних найкоротших шляхів довжини T = 2 + 3 = 5. - Розташуємо контрольний пункт у $(1,1)$, а фініш — у $(2,2)$. Від початку до контрольного пункту є $2$ шляхи, і $2$ шляхи — від контрольного пункту до фінішу. Отже, разом $4$ різних найкоротших шляхи, а T = 2 + 2 = 4.

Як учаснику Hacker Cup, вам потрібно визначити, як розташувати контрольний пункт та фініш, аби не програти. Для кожного $S$ знайдіть мінімально можливу довжину $T$ серед усіх можливих розташувань контрольного пункту та фінішу, для яких існує рівно $S$ різних найкоротших шляхів від початку до фінішу через контрольний пункт.