Pie Shop

View as PDF

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Maniacal Midsummer Marathon 2014 by AL, TL, JJ

Dorian loves pies, and he especially loves his local pie shop - that's why he's bought an all-you-can-eat pie dinner! The pies have been arranged into a grid with rows and columns . The pie in row and column has a tastiness value . Dorian is a messy eater, and whenever he eats a pie, he destroys all pies adjacent to it. He would like to maximize the sum of the tastiness values of the pies he eats, and also figure out how many ways he can achieve this sum.

Two pies respectively located at and , are adjacent if they are exactly unit of distance apart; that is, .

Input Specification

The first line contains two space-separated integers and .
The next lines each contain space-separated integers representing the tastiness values of the pies.

Output Specification

A single line containing two space-separated integers: the maximum possible sum and the number of ways to reach this sum. Since the number of ways may be very large, you should give the value modulo ().

Sample Input 1

3 4
1 2 3 1
5 7 2 1
1 4 1 0

Sample Output 1

14 3

Sample Input 2

3 3
1 1 0
0 0 1
1 1 0

Sample Output 2

3 5

Scoring

If your output is incorrectly formatted, then your program will score points.
Otherwise, if you correctly determine the first number but not the second, then your program will score of points for the test case.
If both numbers are correct, then you will receive of points for the test case.