# DCP-218: Pacman Back to All Problems

Medium Divide and Conquer > Dynamic Programming

In this problem, you will be given a 2D matrix with **N** rows and **M** columns. There is a Pacman in the (1,1) position. He can move only to right or only to down. Each cell of the matrix contains some coin values. If Pacman moves to a cell then he earns that amount of coin value that the cell contains. Your task is to calculate the maximum number of coins the Pacman can earn if he wants to reach to the cell (N,M). Input: ------ First line of input contains an integer **T** that denotes the number of test cases **(T<=100)**. Next line contains two integers **N** and **M** separated by space **(1 <= N,M <=100)**. Next N lines contains M integers separated by space which denotes the coin value of that cell. **(coin value <=1000)** Output: ------- For each set of inputs, print a single integer in a single line, the maximum coin values that Pacman can earn Sample Input ------------ 2 5 6 1 6 2 3 4 5 9 1 2 1 8 6 2 5 8 6 10 5 8 5 9 4 2 8 23 5 8 5 9 6 2 3 1 5 3 4 2 6 Sample Output ------------- 76 15

### Problem Limits

 Language Time Limit (seconds) C 2.00 C++ 2.00 C++14 2.00 C# 3.00 Go 3.00 Java 3.00 JavaScript 3.00 Objective-C 3.00 Perl 3.00 PHP 3.00 Python 3.00 Python3 3.00 Ruby 3.00 VB.Net 3.00

# 52/86

Solve/Submission

### Ranking

# User Language Timing
01 MAHRahat Cpp14 0.02s
02 rayhan50001 Cpp14 0.02s
03 SakibAlamin Cpp14 0.02s
04 vatsalsharma376 Cpp14 0.02s
06 Morass Cpp14 0.03s
07 traveller42 Cpp14 0.03s
08 feodorv Cpp14 0.03s
09 nazmul_bzs Cpp14 0.03s
10 sakib_muhit Cpp 0.03s
11 umli Cpp14 0.03s
12 tariqiitju Cpp14 0.03s
13 Masum_ice Cpp14 0.03s
14 Ishrak Cpp14 0.03s
15 ash12 Cpp14 0.03s
16 anowar1112 Cpp14 0.03s
17 haasib Cpp14 0.03s
18 seyedssz Cpp14 0.03s
20 prateepm Cpp14 0.03s
21 Sarwar05 Cpp 0.03s
22 Protap_Ghose Cpp 0.03s
23 mahmud2690 Cpp14 0.04s
24 abdulmukit Cpp 0.04s
25 Robbinb1993 Cpp 0.04s