题目背景

第十三届蓝桥STEMA青少年组2022年3月C++组第4题

题目描述

果园有 m 行 n 列桃树，每棵桃树上有一定数量的桃子。猴子从左上角的桃树开始进入果园摘桃子，每到达一棵桃树下都会将树上的桃子摘完，但猴子每次只能移动到当前所在桃树的下边或右边的桃树下摘桃子，按照这样的移动方案，猴子在果园中最多可以摘到多少桃子。

现给出 m 和 n 的值，及每棵桃树上的桃子数量，按照移动方案，计算出猴子在果园最多可以摘到多少桃子。

例如：m = 2，n = 3，桃子数量为：
2 3 1
1 4 2

这种情况下，为了摘到最多数量的桃子，猴子摘桃子的顺序应为2，3，4，2，总桃子数为 11。

输入格式

第一行输入两个正整数 $m，n（1≤m≤20，1≤n≤20）$，m 表示果园桃树的行数；n 表示果园桃树的列数；两个正整数之间一个空格隔开。

第二行输入 m 行数据，每行 n 个正整数$（1≤正整数≤1000）$，正整数表示每棵桃树上的桃子数量，正整数之间一个空格隔开。

输出格式

输出一个整数，表示猴子在果园中最多可以摘到多少桃子。

样例 #1

样例输入 #1

2 3
1 4 5
5 4 6

样例输出 #1

16