14070번 - Roj 다국어

Olujno nevrijeme razbacalo je roj pčela po koordinatnoj ravnini te se svaka pčela trenutno nalazi u nekoj točki s cjelobrojnim koordinatama. Sve pčele žele se naći u istoj točki, takoder sa cjelobrojnimkoordinatama. Pčele iz ovog roja dijele genetsku mutaciju zbog koje mogu letjeti samo u odredenimsmjerovima. Dozvoljeni smjerovi su podskup skupa svih glavnih i sporednih strana svijeta. Kao i obično, sjever je smjer rastuće y koordinate dok je istok smjer rastuće x koordinate.

U svakom koraku, jedna pčela može se pomaknuti na susjednu točku sa cjelobrojnim koordinatama u jednom od dozvoljenih smjerova. Pronadite najmanji ukupan broj koraka potreban da se sve pčelenadu u istoj točki. 

Ilustracija prvog primjera test podataka

U prvom redu nalazi se cijeli broj d (1 ≤ d ≤ 8) — broj dozvoljenih smjerova. Drugi red sadrži d različitih nizova znakova odvojenih s po jednim razmakom. Svaki niz znakova je jedan od N, NW, W, SW, S, SE, E, NE koji redom označavaju sjever, sjeverozapad, zapad, jugozapad, jug, jugoistok, istok i sjeveroistok.

U sljedećem redu nalazi se prirodni broj n (1 ≤ n ≤ 50) — broj pčela. U k-tom od sljedećih n redova nalaze se cijeli brojevi x_k i y_k (−10⁶ ≤ x_k , y_k ≤ 10⁶ ) — koordinate točke u kojoj se trenutno nalazi k-ta pčela. Možete pretpostaviti da se sve pčele nalaze u različitim točkama.

Ispišite traženi najmanji ukupan broj koraka. Možete pretpostaviti da rješenje uvijek postoji.