github.com/captn3m0/codechef.git

---
{"category_name":"easy","problem_code":"OLDFAR","problem_name":"Old Farmer","languages_supported":{"0":"C","1":"CPP14","2":"JAVA","3":"PYTH","4":"PYTH 3.6","5":"PYPY","6":"CS2","7":"PAS fpc","8":"PAS gpc","9":"RUBY","10":"PHP","11":"GO","12":"NODEJS","13":"HASK","14":"rust","15":"SCALA","16":"swift","17":"D","18":"PERL","19":"FORT","20":"WSPC","21":"ADA","22":"CAML","23":"ICK","24":"BF","25":"ASM","26":"CLPS","27":"PRLG","28":"ICON","29":"SCM qobi","30":"PIKE","31":"ST","32":"NICE","33":"LUA","34":"BASH","35":"NEM","36":"LISP sbcl","37":"LISP clisp","38":"SCM guile","39":"JS","40":"ERL","41":"TCL","42":"kotlin","43":"PERL6","44":"TEXT","45":"SCM chicken","46":"PYP3","47":"CLOJ","48":"COB","49":"FS"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"sahil070197","problem_tester":null,"date_added":"20-10-2018","tags":{"0":"sahil070197"},"time":{"view_start_date":1540578600,"submit_start_date":1540578600,"visible_start_date":1540578600,"end_date":1735669800},"is_direct_submittable":false,"layout":"problem"}
---
<span class="solution-visible-txt">All submissions for this problem are available.</span>Old Farmer Ranjan works on the farm of landlord Mittal Sahab. On the occasion of Diwali, Mittal Sahab decided to give some bonus to the hardworking farmer Ranjan. Mittal Sahab promised him to offer all the dragon fruits that Ranjan collects in one go from the right side of the farm returning back to the same side, such that he can take exactly 2 left turns.
Ranjan farmer can start plowing from any cell $A[i][N]$ where 1 <=$ i$ <= N. 
The farm is represented as a 2D matrix, each cell consisting of some units of dragon fruit. Ranjan farmer wants to collect as much amount of dragon fruits as possible, but he is illiterate so he gave this job to his son, the great coder Rishi.
Please refer to the image below for more clarification on how to traverse the farm.
<img src="https://codechef_shared.s3.amazonaws.com/download/HYC/External_contest_images/ENCO2018/OLDFAR/OLDFAR.png">


###Input

- The first line contains single integer $T$, denoting the number of test cases.
- The next line consists of 2 space separated integers $N$ and $M$, denoting the dimension of the farm.
- The next $N$ lines consist of $M$ space separated integers each denoting the amount of dragon fruit in the cell.


###Output:
Output a single integer denoting the maximum amount of vegetable Ranjan farmer could collect.

###Constraints 
- $1 \leq T \leq 5$
- $2 \leq N,M \leq 10^3$
- $2 \leq A[i][j] \leq 10^9$ for  $1 \leq i,j \leq N,M respectively$


###Sample Input:
	2
	3 3
	1 2 3
	3 3 1
	4 1 6
	3 3
	3 7 4
	1 9 6
	1 7 7

###Sample Output:
	20
	34