Under construction

Still being built. Things may change

Resource Mining

Interview

Time limit2sMemory limit256 MB

Summary
A robot walks from the top-left to the bottom-right cell of an N by M grid using only right and down moves; find the largest number of resource cells it can pass through.
Level

Medium4 of 10

Topics
Dynamic programming, Matrix, Greedy, Implementation
Solved
No attempts yet

Problem

WOOK is a next-generation AI robot that mines resources in place of humans. WOOK always stays inside a fixed area. It starts at the top-left cell (1,1)(1, 1) and explores for resources on its way to the bottom-right cell (N,M)(N, M).

In one move, WOOK can go one cell to the right or one cell down. It cannot move in any other direction. WOOK can collect a resource only when the cell (x,y)(x, y) it is standing on holds one. The start and end cells count as well.

Given the map of the area, find the maximum number of resources WOOK can collect.

Input

The first line contains the height NN and the width MM of the area (1≤N,M≤3001 \le N, M \le 300).

Each of the next NN lines contains MM space-separated numbers describing the area. A cell with a resource is 1, and empty ground is 0.

Output

Print the maximum number of resources WOOK can collect.

Examples1

  1. Example 1

    Input
    5 4
0 1 0 0
0 0 1 0
1 1 0 0
1 0 1 0
1 1 0 0
    Expected output
    4