Прямокутний острів розділений на квадрати, тому його розміри – \(N\) на \(M\) квадратів. У кожному квадраті з координатами ( \(i , j\) ) (спочатку вказується рядок, потім стовпець) зарито \(Z_{ij}\) золотих монет. Карта розташована так, що північ відповідає напрямку нагору. Комірки в рядках і стовпцях нумеруються з одиниці, верхній лівий кут має координати (1, 1) .

Пірат хоче пройти з південно-західного кута острова в північно-східний, причому на кожному кроці він може рухатися тільки на північ або лише на схід, переходячи до наступного квадрата.

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

Формат вхідних даних

У першому рядку вводяться два натуральні числа: \(N\) і \(M\) ( \(2 \le N , M \le 1000\) ), розділені пробілом.

У кожному з наступних \(N\) рядків записані через пробіл по \(M\) чисел, які позначають кількість монет, заритих у кожному квадраті острова (квадрати перераховуються по рядках із півночі на південь, у кожному рядку – із заходу на схід).

Формат вихідних даних

У першому рядку програма має вивести найбільшу кількість монет, яку може зібрати пірат.

У другому рядку без пробілів виводяться кроки, які потрібно виконати пірату: літера 'E' (від слова east) позначає крок на схід, а літера 'N' (від слова north) – крок на північ.

Приклад вхідних даних

3 3
1 2 3
2 5 7
1 3 2

Приклад вихідних даних

19
ENEN