Description

An ancient pyramid has treasures on each level. Starting from the top, collect treasures as you descend to the bottom. At each position, you can only move to the cell directly below or diagonally right-below. Find the maximum sum of treasures you can collect.

Input

Output

Constraints

• •1 <= rows <= 500
• •-10000 <= each value <= 10000

Examples

[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4]]

22