31239번 - ТВ ИГРА 스페셜 저지다국어

В една известна телевизионна игра играч се намира пред вертикално правоъгълно табло с размери N реда на М колони. Той има възможност да избере някоя от колоните и да пусне в нея топче. Топчето започва да пада надолу като последователно преминава през различни клетки докато не достигне до дъното на правоъгълното табло. По своят път надолу то може да преминава от една колона в друга, като попада в клетки, означени със следните знаци:

• ‘.’ – от тази клетка топчето ще продължи своето падане право надолу. Тоест, ако е било в клетка на ред i и колона j със стойност ‘.’ то ще отиде в клетка с ред i+1 и колона j.
• ‘L’ – от тази клетка топчето ще продължи своето падане наляво. Тоест, ако е било в клетка на ред i и колона j със стойност ‘L’ то ще отиде в клетка в ред i+1 и колона j-1.
• ‘R’ – от тази клетка топчето ще продължи своето падане надясно. Тоест, ако е било в клетка на ред i и колона j със стойност ‘R’ то ще отиде в клетка в ред i+1 и колона j+1.
• ‘X’ – топчето се спира в тази клетка и играчът определя накъде то да продължи да пада. Той има три възможности – към долната лява клетка, към долната клетка или долната дясна клетка.
• Цифра от 0 до 9 (включително) – играчът прибавя стойността на цифрата в хиляди левове към своята печалба, а топчето пада в долната клетка ако има такава.

Напишете програма tvgame, която определя колко е най-голямата възможна сума, която играчът може да събере в играта и му показва един възможен начин, по който може да я постигне.

На първия ред на стандартния вход са записани две цели числа N – броят на редовете и M – броят на колоните на таблото. Следват N реда, като всеки от тях съдържа M символа, задаващи игралното табло.

На първия ред на стандартния изход програмата трябва да изведе колко е максималната възможна сума в хиляди левове, която играчът може да събере в играта.

На втория ред на стандартния изход изведете номера на колоната, в която трябва да се пусне топчето, за да постигне съответната сума. На следващия ред отпечатайте пътя на топчето – за всяко преминаване на топчето от една клетка в друга изведете по един символ L, ако топчето продължава към долната лява клетка, символ R, ако топчето продължава в долната дясна клетка или D, ако продължава към долната клетка.

• 0 < N, M < 1000
• Номерацията на редовете и колоните на полето започва от 1. Когато пускаме топче в колона j, то ще попадне първо в клетката от ред 1 и колона j.
• Всички клетки от първата и последната колони, както и от най-долния ред ще съдържат печалби (цифри).