SP8408 MNMXPATH - Min Max 01 Path

I have been asked to set a problem by spoj, what do I do now ? Lets see the standard stuff in most of the programming contests and make one problem out of it. Hmm... many problems are having Binary digits, Grids, Paths, Coins, Maximize or Minimize something, so let me mix them all now in to one problem, the one problem to rule them all ;) Lets have a grid of size **N** x **M** having N rows and M columns, and put gold coins in it. How many in each cell ? , lets involve binary here. I'll give you two binary strings **A**\[1...N\] and **B**\[1...M\]. Cell (i,j) (1-based indexing) Row-i and Column-j in the grid contains A\[i\] \* B\[j\] gold coins. From a cell (i,j), you can move to any of the 4 adjacent cells (i-1,j), (i+1,j), (i,j-1), (i,j+1) in one step. I want a path of _minimum length_ from top-left cell (1,1) to bottom-right cell (N,M), and the value of this path = number of gold coins it covers. Find the maximum value of such a path. Not every one wants to become a Raja, also find the minimum value of such a path.

First line contains T \[ number of test cases, around 10 \]. T cases follow, each having 2 lines, "N A" and "M B" (quotes for clarity only). \[ 1

For each test case, print the maximum value of a path followed by the minimum value of a path, in the same line, separated by a single space. Output of each case should be in a separate line.