C. Чип тоглоом

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

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

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

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

Дараах тоглоомыг авч үзье. Бидэнд $n × m$ хэмжээтэй тэгш өнцөгт талбай өгөгдөх ба талбайн зарим нүдэнд чип байрлана.

Чип бүр дээр чиглэлтэй сум байх ба дараах чиглэлүүдийн аль нэгрүү нь заасан байна: дээшээ, доошоо зүүн эсвэл баруун.

Тоглогч нэг чип сонгон түүн дээр нүүдэл хийнэ.

Нүүдэл нь дараах үйлдлүүдийн дараалал юм. Одоо байгаа чип нь тэмдэглэгдэнэ. Үүний дараа одоо байгаа чип дээрх заасан чигт өөр чип байх эсэхийг шалгана. Хэрэв дор хаяж нэг чип байвал тэднээс хамгийн ойр байгаа чип уруу нүүдэл шилжиж өмнөх чип нь талбайгаас устана. Энэ үйлдэл нь олон дахин давтагдаж болно. Хэрэв шинэ чип олдохгүй байвал одоо байгаа чип нь талбайгаас устгагдаад тоглогчийн нүүдэл нь дуусна.

Нүүдлийн төгсгөлд тоглогч талбайгаас устгагдсан чип-ны тоотой тэнцүү хэмжээний оноо авна.

Анх байсан чипнүүдийн байрлал өгөгдсөн бол тоглогч нэг нүүдлээр авч чадах хамгийн их оноог ол. Мөн ийм нүүдлийн тоог тодорхойл.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ ба $m$ ($1 ≤ n, m, n × m ≤ 5000$) өгөгдөнө. Дараагийн $n$ мөрөнд тус бүр $m$ тэмдэгт өгөгдөнө -- тоглоомын талбайг дүрслэнэ. ".$" гэдэг нь нүд хоосон байна. "L$", "R$", "U$", "D$" гэдэг нь энэ нүд чип агуулах ба сум нь харгалзан зүүн, баруун, дээшээ, доошоо чигт заасан байна гэдгийг илэрхийлнэ.

Талбайд дор хаяж нэг чип заавал өгөгдөнө.

Гаралт

2 тоо хэвлэнэ - нүүдэл хийсний дараа авч чадах хамгийн их оноо ба хамгийн их оноог авах нүүдлийн тоо.

Орчуулсан: Б.Алтангэрэл

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

Оролт
4 4
DRLD
U.UL
.UUR
RDDL
Гаралт
10 1
Оролт
3 5
.D...
RRRLL
.U...
Гаралт
6 2

Тэмдэглэл

Эхний жишээн дээр $(3, 3)$ дээрх чип-г сонгоход хамгийн их оноогоо авна. Дараах зурагнаас үйлдлүүдийг харж болно:

Бусад бүх чип илүү бага оноо авна.

Сэтгэгдлүүдийг ачааллаж байна...