Задача №112613. Пират на острове
Прямоугольный остров разделён на квадраты, так что его размеры – N на M квадратов. В каждом квадрате с координатами ( i , j ) (сначала указывается строка, потом – столбец) зарыто Z ij золотых монет. Карта расположена так, что север соответствует направлению вверх. Ячейки в строках и столбцах нумеруются с единицы, левый верхний угол имеет координаты (1, 1) .
Пират хочет пройти из юго-западного угла острова в северо-восточный, причём на каждом шаге он может двигаться только на север или только на восток, переходя в следующий квадрат. Напишите программу, которая находит наибольшее количество монет, которое может собрать пират, и выводит его маршрут.
В первой строке вводятся два натуральных числа: N и M ( 2 ≤ N , M ≤ 1000 ), разделённые пробелом. В каждой из следующих N строк записаны через пробел по M чисел, которые обозначают количество монет, зарытых в каждом квадрате острова (квадраты перечисляются по строкам с севера на юг, в каждой строке – с запада на восток).
В первой строке программа должна вывести наибольшее количество монет, которое может собрать пират. Во второй строке без пробелов выводятся шаги, которые нужно выполнить пирату: буква 'E' (от слова east ) обозначает шаг на восток, а буква 'N' (от слова north ) – шаг на север.
3 3 1 2 3 2 5 7 1 3 2
19 ENEN