SP8424 BTCODE_F - Life Game

Gobo and Muku were really bored of working and decided to play a game on their respective laptops - the game of life. It is a one player game which consists of an M\*N rectangular grid. Each cell of the grid contains exactly one magical potion. The potion at the j $ ^{th} $ column of the i $ ^{th} $ row of the grid increases the player's current health by V $ _{ij} $ .(This value can be negative, in which case the player's health decreases). At any point of time, the health of a player can be negative too (i.e. He does not die). From a cell(i,j), the player can move to cells (i+1,j-1) or (i+1,j) or (i+1,j+1), as long as these cells exist in the grid. Initially, the player has a health of 0. He can start from any column on the first row (1,j). If he chooses to enter a cell, then he is forced to drink the potion in that cell. The game is completed when any column of the last row is reached. There are 2 modes in which the game can be played: the "min" mode and the "max" mode. In "max" mode, the aim is to finish the game with maximum health H $ _{max} $ satisfying the condition A

The first line of input contains an integer 't', denoting the number of test cases. For each test case, the first line contains 2 space separated integers 'M' and 'N'. The next line contains 2 space separated integers 'A' and 'B'. Each of the next 'M' lines contain 'N' integers. The j $ ^{th} $ integer on the i $ ^{th} $ line denotes the value V $ _{ij} $ .

Output 2 space separated integers H $ _{min} $ and H $ _{max} $ , the minimum and maximum health with which Gobo and Muku can finish the game. H $ _{max} $ and H $ _{min} $ should satisfy A