Plates of Omnipotence
Lord Benedict, in his daring escape from the Black Lord's castle, finds himself in the treasury of the Black Fortress. This treasury is a square room consisting of N×N cells. Benedict starts in the top-left cell, while the exit is located in the bottom-right cell. Some of these cells contain Tiles of Omnipotence. Benedict's goal is to escape the room while traversing as many of these tiles as possible. Although he could potentially visit all the tiles, his "Swiftstep Boots" restrict his movement to only rightward or downward directions, necessitating a strategic choice of path.
Input
The first line provides the integer N (1 ≤ N ≤ 500). The following N lines each contain N integers, representing the layout of the treasury, starting from the top-left cell and ending at the bottom-right cell. A 0 indicates an empty cell, while a 1 denotes a cell containing a Tile of Omnipotence. Notably, the top-left and bottom-right cells do not contain any tiles.
Output
Output the maximum number of Tiles of Omnipotence that Benedict can pass through on his way to the exit.