All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Help Ashwin
Tag(s):

Easy

Problem
Editorial
Analytics

Ashwin wants to make this Valentine special for Disha. So, he wants to collect maximum number of roses. Help him to collect maximum number of roses. Roses are kept in boxes and the boxes are further arranged in a N*M grid.
Ashwin can pick a box and get all the roses it contains,but the hack is that if you choose a box, the box immediately below it cannot be selected. So, help him collect the maximum number of Roses.


*NOTE* : Only one box can be selected from each row

INPUT:
There are T test cases.
For each test case, the first line consists of two integers N and M, denoting the number of rows and number of columns in matrix A respectively. Each of the following N lines consist of M space-separated integers, thus describing the grid.

OUTPUT:
For each test case, output the maximum number of roses Ashwin can collect.

CONSTRAINTS
1 <= T <= 10
2 <= N,M <= 10^5
4 <= N*M <= 10^6
1 <= A[i][j] <= 100

SAMPLE INPUT
1
4 4
1 2 3 4
5 6 7 8
9 1 4 2
6 3 5 7
SAMPLE OUTPUT
27
Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Уведомления
View All Notifications

?