Given a square matrix of integers, find the maximum sum of elements on the way from the top-left cell to the bottom-right cell. From a given cell, you may only move either to the cell to the right or to the cell below. For example, consider the following matrix.

The maximum sum is 29 and is given by the following path.

Your task is to write procedure traverse that takes a square matrix of integers and returns the corresponding answer.

# Solution

Here is a Ruby implementation.