Мишка і зернинки

Ліміт часу 1 секунда

Ліміт використання пам'яті 122 MiB

В індійському храмі підлогу прямокутної форми вимощено однаковими квадратними плитками 1 x 1, на кожну з яких насипано від 0 до k зернинок (k ≤ 30000). Розміри підлоги m х n. Мишка вибігає з лівого нижнього кута підлоги храму i рухається до входу у іншу нірку, розміщену у протилежному кутку. Мишка може рухатись лише праворуч або вперед, збираючи всі зернинки з плитки, на якій вона знаходиться. Знайти маршрут, рухаючись по якому мишка збере найбільшу кількість зернин.

Вхідні дані

Перший рядок містить числа m та n - розміри підлоги (1 ≤ m, n ≤ 100). Далі йде m рядків, починаючи з верхнього, у кожному з яких розміщено n чисел – кількість зернинок на відповідній плитці.

Вихідні дані

Вивести маршрут руху мишки у форматі: RRFFFRF (F - крок вперед, R - крок праворуч).

Приклад

Вхідні дані #1

2 3
3 2 4
1 5 1

Вихідні дані #1

RFR

Вхідні дані #10

10 10
3 2 0 0 0 0 0 0 0 0
0 2 10 0 0 0 0 0 0 0
0 0 9 3 0 0 0 0 0 0
0 0 0 9 2 0 0 0 0 0
0 0 0 0 2 3 0 0 0 0
0 0 0 0 0 4 3 0 0 0
0 0 0 0 0 0 1 5 0 0
0 0 0 0 0 0 0 8 10 0
0 0 0 0 0 0 0 0 1 8
0 0 0 0 0 0 0 0 0 5

Вихідні дані #10

FFFFFFFRRFFRRRRRRR

Автор Анатолій Присяжнюк

Показати класифікацію задачі