C. Петя болон Аалзнууд

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

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

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

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

Петя аалзнуудыг сургах дуртай. Петяд $n × m$ хэмжээтэй хөлөг байгаа. Анх хөлгийн нүд бүр дээр нэг аалз байгаа. Петя аалз бүрт нэг тушаал өгнө. Үүнээс яг нэг хормын дараа бүх аалз өөрт оноогдсон тушаалыг гүйцэтгэнэ. Петя аалзнуудад $5$ төрлийн тушаал өгч чадна. Юу ч хийлгүй зүгээр зогсох эсвэл $4$ хөрш нүднийхээ аль нэг рүү нүүх (бүх нүүдлийг ялгаатайд тооцно). Петя аль ч аалзыг хөлгөөс гарахгүй байхаар тушаал өгнө. Аалзнууд бие биетээгээ зөрж явж болно. Бүх аалзнууд яг нэгэн зэрэг хөдлөх бөгөөд нэг нүд нь дээр хэдэн ч аалз байраж болно. Петя нэг үйлдлийн дараагаар байж болох хамгийн их аалзгүй нүд хэдийг үүсгэж чадахаа мэдэхийг хүсэж байгаа.

Оролт

Эхний мөрөнд хөлгийн хэмжээ болох $n$, $m$ ($1 ≤ n, m ≤ 40$, $n·m ≤ 40$) хоёр тоо зайгаар тусгаарлагдан өгөгдөнө.

Гаралт

Байж болох хамгийн их аалзгүй нүдний тоо.

Орчуулсан: Энхсанаа, zoloogg

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

Оролт
1 1
Гаралт
0
Оролт
2 3
Гаралт
4

Тэмдэглэл

In the first sample the only possible answer is:

s$

In the second sample one of the possible solutions is:

rdl$  
rul$

s$ denotes command "stay idle", l, r, d, u$ denote commands "crawl left", "crawl right", "crawl down", "crawl up", correspondingly.

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