Йою Ньерк

Smon Jeet ilk dəfədir ki, Yoyu Nyerk-ə gəlib. Buna görə də o, bu nəhəng şəhərdə zəif istiqamətlənir.

Şəhərin yollarının quruluşu olduqca sadədir. Şəhərin yolları şərqdən qərbə doğru uzanan $n$ küçədən və şimaldan cənuba doğru uzanan $m$ prospektdən ibarətdir. Bütün küçələr şimaldan başlayan ən şimaldakı küçədən başlayaraq $1$-dən $n$-ə kimi nömrələnib. Prospektlər də qərbdən başlayan ən qərbdəki prospektdən başlayaraq nömrələnir. Bütün qonşu küçə və prospektlər arasındakı məsafə eynidir. Bütün küçələr və prospektlər bir istiqamətlidir.

Smonun əlində şəhərdəki bütün yolların istiqamətlərini göstərən xəritə var. Smon bilir ki, hazırda $a$-cı prospekt ilə $s$-ci küçənin kəsişməsindədir. O, avtomobilinə $b$-ci prospekt ilə $t$-ci küçənin kəsişməsində minmək istəyir. Ona ən yaxşı marşrutu tapmaqda kömək edin.

Marşrut — Smonun necə hərəkət etməli olduğunu təsvir edən bir yol təsviridir. Bu təsvir ardıcıl $c[i]$ ədədlərdən ibarətdir, belə ki, birinci kəsişmədən birinci dönməyə qədər $c[1]$ blok getmək, sonra dönüb növbəti dönməyə qədər $c[2]$ blok getmək və s. lazımdır. Marşrut təsvirindəki sonuncu ədəd son dönmədən yolun son nöqtəsinə qədər məsafəyə uyğundur. Marşrutun uzunluğu ona uyğun olan yolun uzunluğudur. Smon Jeet hesab edir ki, qısa marşrutlar uzunlardan daha yaxşıdır. Eyni uzunluğa malik marşrutlar arasında, daha az dönməsi olan marşrutlar daha yaxşıdır. Həm uzunluq, həm də dönmə sayı eyni olan marşrutlar arasında, minimum $c[i]$ maksimal olan marşrut daha yaxşı sayılır. Qalan marşrutları isə Smon bərabər hesab edir.