CWORLD - A Colorful world

no tags 

This is the hardest level of the game. There are n stages in the level. In each stage you will given qi balls. The color of the balls are denoted by an integer between 1 to k. You can pick up not more than one ball in each stage. (You can skip if you want) If you pick up a ball you will gain or lose some points depending on the last ball you have picked. You know color of the available balls of each stage and points you'll get for a certain combination, now can you figure out the maximum point you can get?

Note that you wont gain or lose any point for the first ball you picked. One stage can contain multiple balls of same color.

Input Specification:
First line of input will contain number of test cases T.

In each case first line will contain two integer n and k. Than there will be n lines which describes each stage. Each line contains an integer qi which denotes number of balls available in ith level and then qi integers will denote the colors.

Then there will be a k lines, each containing k integer, jth integer of ith line will indicate the point you will gain or lose if you pick a ball of color j after color i. Negative means you will lose point.

Output Specification:

Print case number and a single integer denoting the maximum point you can get.






point gain or lose in a step will be at most 1000.

Sample Input


2 3

3 2 3 2

4 1 1 3 3

1 5 0

1 0 2

-4 1 -5

4 4

1 4

2 3 1

2 2 4

3 4 2 2

-5 -2 3 2

-5 -1 2 0

3 4 5 -4

-3 -5 0 -4

Sample output:

Game 1: 2

Game 2: 4


In first case you can pick color 2 in first stage and color 3 in second stage in gain 2 points.

hide comments
RAJDEEP GUPTA: 2014-09-30 13:31:39

@[bLanK]: You need to work on the stages in order. So, you cannot go to stage 2 before stage 1. This should have been mentioned although.

reply : thanx for the clarification !

Last edit: 2014-06-30 16:57:43
BLANKRK: 2014-09-30 13:31:39

in first test case cant we pick ball color 1 from 2nd stage and then ball color 2 from 1st stage and gain point 5????

Last edit: 2014-06-24 15:23:29
Ashwini: 2014-09-30 13:31:39

my 50th. :)
didn't notice at most at first. caused me 2 wa. ac finally. nice dp problem though

Andy: 2014-09-30 13:31:39

2>=n<=100 is the same as n<=2?

Rishav Goyal: 2014-09-30 13:31:39

yeah !! nice too hai :D

Samuel Nacache: 2014-09-30 13:31:39

Nice dp problem

રચિત (Rachit): 2014-10-03 05:59:13

"You can pick up not more than one..." Can you avoid picking ball?
As it turns out, you can avoid picking ball. IMHO, it could have been mentioned clearly in the statement.

Last edit: 2014-04-21 09:53:02
nani: 2014-09-30 13:31:39

can someone give more test cases?

Last edit: 2014-04-16 10:17:42

Added by:Shafaet
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem, Bangladesh Informatics Olympiad 2012