Hello Kitty's Peanuts

Problem Description

Hello Kitty wants to pick some peanuts to give to her favorite Mickey Mouse. She comes to a rectangular peanut field with grid-like roads (as shown in the figure below), entering from the northwest corner and exiting from the southeast corner. At every road intersection in the field there grows a peanut plant with a number of peanuts on it; passing a peanut plant lets her pick all the peanuts on it. Hello Kitty can only walk east or south, never west or north. What is the maximum number of peanuts Hello Kitty can pick?

Input Format

The first line is an integer $T$, the number of data groups in total ($1 \le T \le 100$).

This is followed by $T$ data groups.

The first line of each data group contains two integers, the number of rows $R$ and the number of columns $C$ of peanut plants ($1 \le R, C \le 100$).

The next $R$ lines of each data group describe the peanut plants in each row, from north to south. Each line contains $C$ integers, describing the number of peanuts $M$ on each plant in that row from west to east ($0 \le M \le 1000$).

Output Format

For each input data group, output one line with the maximum number of peanuts Hello Kitty can pick.

2
2 2
1 1
3 4
2 3
2 3 4
1 6 5

8
16

Source

一本通在线评测