284. Snakes

Problem Statement:
Remember before smartphones, Snake was the coolest mobile game ever. It required speed, accuracy and practice, and only a few managed to win this game at its highest difficulty.

The game's purpose is to guide a snake to collect randomly appearing dots in the maze. Each turn the snake's head either moves forward in the same direction, or turns left or right. The snake dies if it intersects its own body.

Saad Nabiha has a much simpler version of the game to win. Given a 2d grid (N rows and M columns), with each cell containing a non-negative integer. He wants to guide a snake with infinite length from the top-most left-most cell in the grid to the bottom-most right-most cell, and maximize the sum of the values of the visited cells. Since the snake has infinite length, it can only visit a cell once. Simple, right?!

Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1  ≤  T  ≤  100). Followed by T test cases. Each test case will consist of a single line, containing five integers separated by a single space: N, M, V, A, B (1  ≤  N, M  ≤  104 , 1  ≤  N  ×  M  ≤  107 , 1  ≤  V, A, B  ≤  104) representing the dimensions of the grid and parameters to generate the values in the grid.

The top-most left-most value will equal V, then the grid will be generated one cell at a time in row major order with the following formula: Vi = (A × Vi - 1 + B) modulo (104 + 7).

Output Format:
For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1) followed by a single space, followed by the maximum sum of values.

Sample Input:
1 2 3 1 2 3

Sample Output:
Case 1: 234

Notes:
For the input test case, the grid is:

1 5 13
29 61 125

 Added by: ahmed_aly Added at: 2014-10-11 15:00:01 UTC Time Limit: 7 seconds Partial score: No Source: ACM Egyptian Collegiate Programming Contest 2014