shunfurh
编程介的小学生
2017-10-29 08:59

Golden Eggs

  • as
  • color
  • it
  • lines
  • each

Problem Description
There is a grid with N rows and M columns. In each cell you can choose to put a golden or silver egg in it, or just leave it empty. If you put an egg in the cell, you will get some points which depends on the color of the egg. But for every pair of adjacent eggs with the same color, you lose G points if there are golden and lose S points otherwise. Two eggs are adjacent if and only if there are in the two cells which share an edge. Try to make your points as high as possible.

Input
The first line contains an integer T indicating the number of test cases.
There are four integers N, M, G and S in the first line of each test case. Then 2*N lines follows, each line contains M integers. The j-th integer of the i-th line Aij indicates the points you will get if there is a golden egg in the cell(i,j). The j-th integer of the (i+N)-th line Bij indicates the points you will get if there is a silver egg in the cell(i,j).

Technical Specification
1. 1 <= T <= 20
2. 1 <= N,M <= 50
3. 1 <= G,S <= 10000
4. 1 <= Aij,Bij <= 10000

Output
For each test case, output the case number first and then output the highest points in a line.

Sample Input
2
2 2 100 100
1 1
5 1
1 4
1 1
1 4 85 95
100 100 10 10
10 10 100 100

Sample Output
Case 1: 9
Case 2: 225

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

1条回答

为你推荐