BTCODE_F - Life Game

no tags 

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 jth column of the ith row of the grid increases the player's current health by Vij.(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 Hmax satisfying the condition A <= Hmax <= B. Similarly, in "min" mode the aim is finish the game with minimum health Hmin, satisfying the conditions A <= Hmin <= B. Now, Gobo decides to play the game in "max" mode on his laptop, and Muku decides to play the game in "min" mode on his laptop. Can you help Gobo and Muku finish with maximum and minimum health respectively, satisfying the above conditions?

Input

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 jth integer on the ith line denotes the value Vij.

Output

Output 2 space separated integers Hmin and Hmax, the minimum and maximum health with which Gobo and Muku can finish the game. Hmax and Hmin should satisfy A <= Hmax, Hmin <= B. If it is not possible to achieve such a health, output "NO" (quotes for clarity).

Gobo and Muku start playing on 2 different instances of the same game independently. i.e. the values of A, B and initial values of Vij are same for both grids.

Example

Input:
2
3 3
5 10
2 5 10
-1 -10 3
-3 6 -2
2 3
8 11
2 5 10
-1 -10 2

Output:
6 10
NO NO

Constraints

t <= 10

1 <= M, N <= 25

-1000 <= A <= B < 1000

-25 <= Vij <= 25

Explanation

Test case 1: Take the path (1, 2) → (2, 1) → (3, 2), to get a value 5 - 1 + 6 = 10. Take the path (1, 2) → (2, 3) → (3, 3), to get a value 5 + 3 - 2 = 6.

Test case 2: There is no valid path which satisfies the above conditions.


hide comments
suhash: 2011-07-19 19:46:25

Yeah right! Sorry updated!

(test): 2011-07-19 19:45:31

In the Output description, should it be "... the minimum and the maximum health with ..."


Added by:suhash
Date:2011-02-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Bytecode 2011, NIT Trichy, India