Дослідники
Чергова космічна експедиція, відправлена на Марс, таки знайшла на ньому життєві форми. Українські космонавти-дослідники Єгор Кулвасéнко та Петро Камрáбов виявили маленьких істот, схожих на звичайних земних мишок.Повертаючись на планетарну станцію після однієї з вилазок на поверхню планети, космонавти спостерігали дивовижну картину: марсіанські „мишки” зібралися у групки на прямокутному плато, яке невідома сила багато тисячоліть тому (як показали дослідження) розбила на квадратні клітинки.
Передавши бортовому комп’ютеру координати плато, вчені отримали у відповідь його мапу. На ній було позначено, скільки марсіанських „мишок” знаходиться у кожній клітинці, та які клітинки непрохідні (мають смертельний рівень радіації).
Вчені на мапі розташовувалися у правому верхньому кутку.
Дослідники одразу зрозуміли, що запаси кисню у них обмежені, тому рухатись по плато вони зможуть лише у напрямку станції: ліворуч або униз. Вони вирішили пройти по плато з правого верхнього у лівий нижній його кут так, щоб наловити найбільшу кількість марсіанських мишок, не ступаючи при цьому у клітинки з підвищеним рівнем радіації. Допоможіть дослідникам у пошуках оптимального шляху.
Вхідні дані
Перший рядок файлу містить розміри плато M та N, які не перевищують 150. Наступні M рядків по N цілих чисел містять опис плато. Якщо число невід’ємне, то воно означає кількість мишок на даній клітинці. Якщо ж число -1, то така клітинка вважається непрохідною. Усі числа не перевищують 10^5.
Вихідні дані
Визначте максимальну кількість мишок, яких можуть впіймати дослідники, та запишіть її у єдиний рядок вихідного файлу.