Write the function CountingApples that takes as input a 2D array apples, and the values of two integers NN and MM (2\leq N,\ 2\leq M)2N, 2M). NN represents the number of rows, and MM represents the number of columns in the given apples 2D array.

You will not be asked to read the values, the apples 2D array will be ready automatically and fed to your CountingApples function.

If there is no path from start to end, the maximum number of collected apples will be 0. Also, if the start cell is a blocked one, there is no solution and the maximum number of collected apples will be 0 in this case as well.

Output

Your function should return the maximum number of apples that can be collected.

Note:

The program will be automatically tested by calling your CountingApples(int** apples, int N, int M) function. You are not allowed to change the signature of this function. Inside the function, you can use apples as a 2D array. You can define additional functions if you need. The function should return the maximum number of apples that can be collected.

Example 1:

N=4 M=5

10 20 30 40 50

5 5 5 5 5

1 1 1 1 1

3 3 3 3 3

Result is 159

Explanation: it will select the path of going the first row and last column

Example 2:

N=4 M=5

4 -1 30 40 50

1 -1 5 5 5

1 -1 1 1 1

1 1 1 1 1

Result is 11

Explanation: Since some cells are blocked, it will select the path of going the first column down and then the last row left to right

Consider the "Collecting Apples" problem given in class, rewrite the solution such that moving from start to end includes three types of moves: Right, Down, Right-Down. The Right-down move means that you can move diagonally. Also, black apples indicate that these are blocked and cannot be crossed as part of the path from start to end. The blocked cells are represented by negative values in the input. Write the function Countingapples that takes as input a 2D array apples, and the values of two integers N and M(2N,2M). N represents the number of rows, and M represents the number of columns in the given 2D array. You will not be asked to read the values, the apples 2D array will be ready automatically and fed to your function. If there is no path from start to end, the maximum number of collected apples will be 0 . Also, if the start cell is a blocked one, there is no solution and the maximum number of collected apples will be 0 in this case as well