VPL0_D - Drastic Grapes

no tags 

It’s December 31st. New year’s Day. Lino and his family are waiting to eat grapes as part of one Venezuelan tradition to ask for wishes to become the New Year. Lino’s parents do it because of the tradition while his little sister Shouri gives a priority to each wish according to its importance, If she has a wish with P priority she must eat a grape with P power, however, the grapes are on the table and she is not tall enough to take them and she gives Lino a list of size N with her priorities. In addition, Lino has another list of size M given by his mother with a brief description of the grapes on the table. Grapes have different characteristics and Lino’s mission is to maximized Shouri’s wishes but with some restrictions:

  • Lino only takes grapes with the same priorities and power.
  • Lino can only take the i-th grape on the table if and only if the grapes taken before and the new one are in the same order in both lists, in other words, if there is on the list of priorities {5,4,1,3,2} and the grapes on the table are {7,1,5,4,9,3,2,1,2,0}, he can choose {4,2} or {4,3,2} but never {1,4} or {1,2,3,4}
  • if Lino can choose between grapes {1,2,3} and {4,5} he choose the ones with the maximum power {4,5}
  • if Lino encounters two groups of grapes with the same power, he will choose the biggest group, example, between {4,5} and {3,3,3} he will choose {3,3,3}.

Input

The first line contains an integer T , which specifies the number of test cases. Then, will follow the descriptions of T test cases.

Each line contains two integers K and N , denoting, respectively, the list of grapes that Shouri holds and the grapes that are on the table. After that, follows a line containing K integers with the description previously mentioned and another line with N integers with the description mentioned too.

The input must be read from standard input.

Output

For each input case you must print the string "Scenario #i: " where i denotes the test case you are evaluating (starting by 1) followed by two numbers, each one denoting the maximum power achievable and the number of grapes to be taken. If there are no group that can satisfy Shouri’s needs, then print 0 0 as maximum power and maximum number of grapes.

The output must be written to standard output.

Sample

Input
3
3 3
1 2 3
3 2 1
3 3
2 4 5
3 2 5
5 7
3 3 3 4 5
4 5 3 8 3 12 3

Output
Scenario #1: 3 1
Scenario #2: 7 2
Scenario #3: 9 3

Subtask 1 - 20%

  • 1 ≤ T ≤ 100
  • 1 ≤ K ≤ N
  • 1 ≤ N ≤ 15

Subtask 2 - 30%

  • 1 ≤ T ≤ 100
  • 1 ≤ K ≤ N
  • 1 ≤ N ≤ 100

Subtask 3 - 50%

  • 1 ≤ T ≤ 20
  • 1 ≤ K ≤ N
  • 1 ≤ N ≤ 1000


hide comments
Jacob Plachta: 2014-08-28 16:51:23

I'd say this problem is very confusingly worded - it's really just asking for the "best" common subsequence of the two sequences. Also, it seems that the values don't exceed 10^4.

tuhin: 2013-06-08 19:11:30

@Venezuelan programming league
please check solution for submission id 9443265. getting correct answer for all test cases . but still WA


Added by:Venezuelan Programming League
Date:2012-12-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for VPL0-Contest