eolymp
bolt
Try our new interface for solving problems
Məsələlər

MaxSum (прыжки в любой столбик)

MaxSum (прыжки в любой столбик)

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Задана прямоугольная таблица размером n строк на m столбцов. В каждой клетке записано целое число. По ней можно пройти сверху вниз, начиная из любой клетки верхней строки, дальше каждый раз перепрыгивая в любую клетку следующего ряда (иными словами, из клетки с номером (i, j) можно перепрыгнуть в любую из клеток (i + 1, 1), (i + 1, 2), ..., (i + 1, m)) и закончить маршрут в какой-нибуть клетке нижней строки.

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

Giriş verilənləri

В первой строке записаны количество строк n и количество столбцов m (1n, m200). Далее в каждой из следующих n строк записано ровно m целых чисел (каждое не превышает по модулю 10^6) - значения клеток таблицы.

Çıxış verilənləri

Вывести единственное число - найденную максимальную сумму.

Nümunə

Giriş verilənləri #1
4 3
1 15 2
9 7 5
9 2 4
6 9 -1
Çıxış verilənləri #1
42
Müəllif Илья Порублёв
Mənbə Летняя школа Севастополь 2013, Волна 1, День 2