Nəzarət nöqtəsi

Siz $(0,0)$ başlanğıc nöqtəsindən başlayaraq (M, N) nöqtəsinə doğru hərəkət etdiyiniz 2D barmaqlıq şəbəkəsində yarışırsınız; burada $M$ və $N$ müsbət tam ədədlərdir və 0 < M \leq N. Yolda bir nəzarət-buraxılış məntəqəsi (çəkpoint) var ki, o nə başlanğıc, nə də finiş nöqtəsinə uyğun gəlmir və $(m,n)$ koordinatında yerləşir; burada 0 \leq m \leq M və 0 \leq n \leq N. Siz hökmən finişə çatmadan öncə çəkpoint-dən keçməlisiniz. Ən qısa yolun uzunluğu T = M + N-dir.

Hər nöqtədən siz sabit sürətlə dörd ən yaxın qonşu nöqtədən birinə hərəkət edə bilərsiniz. Lakin yarışı uduzmamaq üçün hər addımda yalnız sağa və ya yuxarı hərəkət edəcəksiniz.

Hədəfə çəkpointdən keçməklə çatmağın bir çox yolu olsa da, yarış asan görünür, çünki həmişə ən qısa marşrutu tapmaq asandır. Amma yarış daha maraqlı olsun deyə qaydalar dəyişir. Artıq daima eyni (M, N) nöqtəsinə qaçmaq əvəzinə, yarışçılar $(x,y)$ finiş nöqtəsini və çəkpoint koordinatlarını elə seçə bilər ki, başlanğıc nöqtəsindən çəkpointdən keçməklə finişə çatmağın dəqiq $S$ fərqli ən qısa yolu olsun.

Məsələn, S = 4 üçün finiş və çəkpoint yerlərinin iki mümkün variantı:

- Çəkpoint-i $(1,3)$, finişi $(2,3)$ yerləşdirin. Başlanğıcdan çəkpointə çatmağın $4$ yolu var. Çəkpointdən finişə çatmağın isə yalnız $1$ ən qısa yolu var. Beləliklə, çəkpointdən keçməklə finişə çatmağın $4$ fərqli ən qısa yolu var və T = 2 + 3 = 5. - Çəkpoint-i $(1,1)$, finişi $(2,2)$ yerləşdirin. Başlanğıcdan çəkpointə çatmağın $2$ yolu, çəkpointdən finişə çatmağın da $2$ yolu var. Beləliklə, ümumilikdə $4$ fərqli ən qısa yol var və T = 2 + 2 = 4.

Hacker Cup yarışçısı kimi, siz elə çəkpoint və finiş yerini seçməlisiniz ki, uduzmayasınız. Verilmiş $S$ üçün, başlanğıc nöqtəsindən çəkpointdən keçərək finişə dəqiq $S$ fərqli ən qısa yol olduğu bütün mümkün çəkpoint və finiş yerləşmələri üzrə ən kiçik $T$-ni tapın.