Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms
• 10
Basic Dynamic Programming
• 11
Recursion
• 12
• 13
Queue & Stack
• 14
Binary tree + BST
• 15
Divide & Conquer + Advanced Sorting
• 16
Heap
• 17
Hashing
• 18
Graph Representation
• 19
BFS

• # Maximum falling path sum

Given a grid of height `h` and width `w`, you are asked to calculate the maximum sum one might obtain by moving from top to bottom, where on each step it’s only allowed to move to the below adjacent 3 cells. In other words, being at position `(r, c)`, you can move to positions: `(r + 1, c - 1)`, `(r + 1, c)`, and `(r + 1, c + 1)`. That’s why we call it a falling sum - as we fall from the top to the very bottom of the grid. Find the maximum sum of the path.
 ㅤ o ㅤ ㅤ ↙️ ⬇️ ↘️ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ

#### Input

The first line of the input contains two integers `h` and `w` (1 ≤ h, w ≤ 100).
The next `h` lines contain `w` numbers (-100 ≤ ≤ 100) representing the values of the grid at row `r` and column `c`.

#### Output

The program should print the maximum possible sum obtained among all the possible falling paths.

#### Examples

 Input Output 3 3 2 1 3 6 5 4 7 8 9 17

#### Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB