提示: 欢迎访问OurACM平台。
Problem 1394 Kingdoms

Accept: 32    Submit: 55
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Given a board with 5 rows (numbered 0 to 4 from top to bottom) and 5 columns (numbered 0 to 4 from left to right), there are two types of tiles will place on it: market place and resource. A resource tile modifies the amount of money to be made by the market place. You are now asked to write a program to determine the maximum profit could be gain by allocating resource tiles.

Details description:

Market Place: The market place tiles are placed on the board that it cannot be reallocated. Each market place may have different profit rate which is represented by an integer from 1 to 5. The profit is measured by the sum of the resource tiles that share the same row or column, and then multiply by the market place's profit rate.

Resource: A resource tile contains a numeric value ranged from -10 to 10.

Example:

Given a board with 6 market places located in the grid (0,2),(1,1),(2,0) ,(2,2),(3,3) and (4,4) with profit rate 5,1,3,3,2 and 5 respectively. 19 tiles valued from -10 to 8 are available for pick. The following configuration shows the maximum profit should be made:
Market place is represented by a single character M with a bracket contains an integer to indicate its profit rate in this example.

The profits of each market profit are:
Market place at (0,2) = (3-4+0+6+4+5+8) *5 = 22*5 = 110 Market place at (1,1) = (-4-1-10-6-8+4-9-5) * 1 = -39*1 = -39 Market place at (2,0) = (3-8-7+1-1+2+7)* 3 = -3*3 = -9 Market place at (2,2) = (4+5+8-1+2+7)*3 = 25*3 = 75 Market place at (3,3) = (0-9+2-3-7-10+5-2)*2 = 24*2 = 48 Market place at (4,4) = (6-5+7-2+1-6+8-3)*5 = 6*5 = 30 Total profit = 119

Input

The first line of input contains a single integer T to indicate the number of test cases. For each test case, it begins with two integers m and n (n + m = 25) to specific the number of market place tile and resource tile respectively.

The following m lines each contain three integers r, c and p (0<=r,c<=4, 1 <=p<=5). (r,c) indicate the row and column of the location for a market place profit ratio (p).

The last line of a test case is a set of n integers to specific the value of resource tile available.

Output

For each test cases, print a single line integer of the maximum profit could be gain.

Sample Input

3 6 19 0 2 5 1 1 1 2 0 3 2 2 3 3 3 2 4 4 5 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 10 15 0 0 1 1 0 1 2 0 1 3 0 1 4 0 1 0 4 1 1 4 1 2 4 1 3 4 1 4 4 1 -3 2 -8 -2 9 0 0 7 1 -9 -10 -4 -8 -8 -8 20 5 0 0 1 0 1 2 0 2 3 0 3 4 0 4 5 1 0 1 2 0 2 3 0 3 4 0 4 4 1 5 4 2 1 4 3 2 4 4 3 3 4 4 2 4 5 1 4 1 1 2 2 2 1 3 2 3 4 3 2 5 10 -10 7 0 -3

Sample Output

119 -82 222

Source

2005 HKUST Local Contest

Submit  Back  Status  Discuss