D. Ксениа ба шатрын хүүнүүд

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Ксениа $n\times m$ хэмжээс бүхий шатрын хөлөгтэй. Нүд бүр нь дараах тэмдэгтүүдийн нэгийг агуулна: "<", ">", "^", "v", "#". "#" тэмдэгт агуулах нүд нь хаалттай нүд юм.Бүх захын нүднүүд хаалттай нүд гэдэг нь мэдэгдэж байгаа.

Ксениа шатрын хөлөг дээр 2 хүүгээр тоглоно. Эхлээд тэрээр 2 хүүгээ хөлөг дээр гаргаж тавина. Хаалттай нүднүүд л 2 ширхэг хүүг нэгэн зэрэг агуулж чадна. Хаалттай бус нүдэнд 2 хүү нэгэн зэрэг байж болохгүй.Тоглоомын эхэнд Ксениа 2 хүүгээ хөлөг дээр байрлуулна. Нүүдэл бүрд Ксениа 2 хүү тус бүрийг тухайн хүү байрлах нүдэн дээрх тэмдэгтийн чиглэлийн дагуу хөрш нүд рүү нь шилжүүлнэ (Нүд "#" тэмдэгт агуулж байвал хүү хөдлөхгүй). Ксениа үйлдлүүдээ нэгэн зэрэг хийдэг (2 дахь жишээ тестийг харна уу).

Мэдээж Ксениа онооны төлөө тоглож байгаа. Оноог нь хэрхэн тооцох вэ? Тун энгийн! 1-р хүү хэдэн нүүдэл хийж чадахыг тоолоод мөн 2-р хүү ихдээ хэдэн нүүдэл хийж чадахыг тоолоод нэмээд гарах тоо нь энэ тоглолтоос авах оноо юм.

Ксениа эхэнд хамгийн сайн байрлуулалтыг хийхэд ихдээ хэдэн оноо авч болох вэ гэдгийг сонирхож байна. Түүнд тусалж хариуг олно уу.

Оролт

Эхний мөрөнд шатрын хөлгийн хэмжээг илтгэх $n ,m (1\le n, m\le  2000)$ Дараагийн $n$ бүр $m$ тэмдэгт агуулах ба эдгээр нь шатрын хөлгийг тодорхойлно. Тэмдэгт бүр дараах тэмдэгтүүдийн нэг нь л байна: "<", ">", "^", "v", "#".

Захын нүднүүд хаалттай байна. (ө.х "#" тэмдэгт агуулна).

Гаралт

Ксениа төгсгөлгүй их оноо авч болох бол $-1$ гэж хэвлэ. Үгүй бол түүний авч чадах хамгийн их оноог хэвлэ.

Орчуулсан: Төрбат

Жишээ тэстүүд

Оролт
1 1
#
Гаралт
0
Оролт
3 4
####
#>^{}#
####
Гаралт
3
Оролт
3 4
####
#><#
####
Гаралт
-1
Оролт
7 5
#####
##v##
##v##
#####
##^{}##
##^{}##
#####
Гаралт
4
Оролт
7 5
#####
##v##
##v##
##<##
##^{}##
##^{}##
#####
Гаралт
5
Сэтгэгдлүүдийг ачааллаж байна...