Thank you for participating in Kick Start 2019 Round F.

**Cast**

Flattening: Written by Yossi Matsumoto and prepared by Zhang Chen.

Teach Me: Written and prepared by Jonathan Irvin Gunawan.

Spectating Villages: Written by Yossi Matsumoto and prepared by Sadia Atique.

Solutions, other problem preparation, reviews and contest monitoring by Ciprian Olariu, Himanshu Jaju, Jonathan Irvin Gunawan, Kevin Tran, Lalit Kundu, Reyno Tilikaynen, Sadia Atique, Stéphane Henriot, Vivek Dhiman, Yang Xiao, and Zhang Chen.

Analysis authors:

- Flattening: Sadia Atique
- Teach Me: Jonathan Irvin Gunawan
- Spectating Villages: Sandeep Mohanty

Blotch has built a wall.
The wall is made up of **N** sections, numbered from 1 to **N** from left to right.
Since he had built the wall in a hurry, not all the sections are of the same height.
The i-th section of wall is **A _{i}** metres tall.

Blotch would like to fix his wall by rebuilding some of the sections. Blotch can set the height of each section he rebuilds to any height he chooses.

Blotch will be *happy* if the number of indices i (1 ≤ i < **N**) where **A _{i}** ≠

What is the fewest sections of the wall Blotch needs to rebuild so that he will be happy?

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
Each test case begins with a line containing the two integers **N** and **K**, the number of sections of wall and the maximum number of changes in height between adjacent sections, respectively.

The second line contains **N** integers. The i-th integer is **A _{i}**, the height
of the i-th section of wall.

For each test case, output one line containing `Case #x: y`

, where `x`

is the test case number (starting from 1) and
`y`

is the fewest sections that Blotch has to rebuild so that he will be happy.

Time limit: TBD seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

1 ≤ **A _{i}** ≤ 1000, for all i.

0 ≤

2 ≤ **N** ≤ 20.

2 ≤ **N** ≤ 100.

Sample Input

4 8 2 300 100 300 300 200 100 800 500 5 3 100 100 100 100 3 7 3 10 20 40 10 10 30 30 10 2 30 30 60 60 90 90 60 60 30 30

Sample Output

Case #1: 3 Case #2: 0 Case #3: 1 Case #4: 2

In the first sample case, there are **N** = 8 sections of wall, and Blotch will be happy if there are at most **K** = 2 changes in height between adjacent sections.
Blotch can:

- rebuild the 2nd section of wall to have height 300,
- rebuild the 6th section of wall to have height 200, and
- rebuild the 8th section of wall to have height 800.

In the second sample case, there are **N** = 5 sections of wall, and Blotch will be happy if there are at most **K** = 3 changes in height between adjacent sections.
Blotch is already happy with this wall, so he does not need to rebuild any sections.

In the third sample case, there are **N** = 7 sections of wall, and Blotch will be happy if there are at most **K** = 3 changes in height between adjacent sections.
Blotch can:

- rebuild the 2nd section of wall to have height 10.

In the fourth sample case, there are **N** = 10 sections of wall, and Blotch will be happy if there are at most **K** = 2 changes in height between adjacent sections.
Blotch can:

- rebuild the 5th section of wall to have height 60, and
- rebuild the 6th section of wall to have height 60.

Here at Google we love teaching new skills to each other!
There are **N** employees at Google, numbered from 1 to **N**.
There are a total of **S** different skills, numbered from 1 to **S**.
Each employee knows up to 5 different skills.

The i-th employee can *mentor* the j-th employee if there is a skill that the i-th employee knows that the j-th employee does not know.
How many ordered pairs (i, j) are there where the i-th employee can mentor the j-th employee?

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
The first line of each test case gives the two integers **N** and **S**, which are the number of employees and the number of skills respectively.

The next **N** lines describe the skills that each employee knows.
The i-th of these lines begins with an integer **C _{i}** which is the number of skills the i-th employee knows.
Then,

For each test case, output one line containing `Case #x: y`

, where `x`

is the test case number (starting from 1) and `y`

is
the number of ordered pairs (i, j) where the i-th employee can mentor the j-th employee.

Time limit: 40 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

1 ≤ **S** ≤ 1000.

1 ≤ **C _{i}** ≤ 5 for all i.

1 ≤

2 ≤ **N** ≤ 500.

2 ≤ **N** ≤ 5 × 10^{4}.

Sample Input

2 4 100 4 80 90 100 5 1 90 1 80 3 80 90 100 3 30 4 10 11 12 13 4 10 11 12 13 5 25 26 27 28 29

Sample Output

Case #1: 7 Case #2: 4

In Sample case #1:

- (1, 2) is a valid pair since employee 1 knows the skill 100 (also 5 and 80), while employee 2 does not.
- (1, 3) is a valid pair since employee 1 knows the skill 100 (also 5 and 90), while employee 3 does not.
- (1, 4) is a valid pair since employee 1 knows the skill 5, while employee 4 does not.
- (2, 3) is a valid pair since employee 2 knows the skill 90, while employee 3 does not.
- (3, 2) is a valid pair since employee 3 knows the skill 80, while employee 2 does not.
- (4, 2) is a valid pair since employee 4 knows the skill 100 (also 80), while employee 2 does not.
- (4, 3) is a valid pair since employee 4 knows the skill 100 (also 90), while employee 3 does not.

In Sample case #2:

- (1, 3) is a valid pair since employee 1 knows the skill 10 (also 11, 12 and 13), while employee 3 does not.
- (2, 3) is a valid pair since employee 2 knows the skill 10 (also 11, 12 and 13), while employee 3 does not.
- (3, 1) is a valid pair since employee 3 knows the skill 28 (also 25, 26, 27 and 29), while employee 1 does not.
- (3, 2) is a valid pair since employee 3 knows the skill 27 (also 25, 26, 28 and 29), while employee 2 does not.

The countryside of Kickstartia consists of **V** villages (labelled from 1 to **V**), connected by **V**-1 bidirectional roads (labelled from 1 to **V**-1).
The i-th road connects village **X _{i}** to village

Some villages are more beautiful than others. The i-th village has a beauty value of **B _{i}**.
Note that it is possible for a village to have a negative beauty value!

You are going to build lighthouses in some of the villages.
A village is *illuminated* if there is a lighthouse built in it, or there is a lighthouse
built in a village that is directly connected to it by a road.

You may build as many or as few (even zero) lighthouses as you like. What is the maximum possible sum of beauty values of illuminated villages you can obtain?

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
Each test case begins with a line containing the integer **V**, the number of villages.
The second line contains **V** integers. The i-th of these is **B _{i}**, the beauty value of the i-th village.

Then, **V**-1 lines follow. The i-th line gives **X _{i}** and

For each test case, output one line containing `Case #x: y`

, where `x`

is the test case number (starting from 1) and `y`

is
the maximum possible sum of beauty values of illuminated villages you can obtain.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

2 ≤ **V** ≤ 10^{5}.

-10^{5} ≤ **B _{i}** ≤ 10

1 ≤

(

There is exactly one sequence of roads connecting every pair of villages.

1 ≤ **V** ≤ 15.

1 ≤ **V** ≤ 10^{5}.

Sample Input

3 9 -10 4 -10 8 20 30 -2 -3 7 1 4 2 4 4 3 9 4 9 8 7 5 6 7 7 9 4 -2 20 20 20 1 2 1 3 1 4 5 -5 -10 8 -7 -2 5 4 4 3 3 2 2 1

Sample Output

Case #1: 67 Case #2: 58 Case #3: 0

In Sample Case #1, you can place a lighthouse in villages 2 and 7. This illuminates villages 2, 4, 5, 6, 7 and 9, for a total beauty of 4 + 8 + 20 + 30 + (-2) + 7 = 67. There are other possible ways to place lighthouses to achieve this total beauty.

In Sample Case #2, you can place a lighthouse in villages 1, 2 and 3. This illuminates villages 1, 2, 3 and 4, for a total beauty of (-2) + 20 + 20 + 20 = 58. There are other possible ways to place lighthouses to achieve this total beauty.

In Sample Case #3, the best you can do is to place no lighthouses at all! This illuminates no villages for a total beauty of 0.

We can start with an interesting observation, whenever we rebuild a section of the wall, it is equivalent to removing that section. So we can follow two steps,

- Pick a set of sections of the wall to remove.
- Check if in the remaining wall sections, the number of positions where
**A**_{i}≠**A**_{i+1}are less than or equals**K**.

There are 2^{N} possible sets of sections, and for each set, checking if the remaining sections will make Blotch happy or not will
take O(**N**) time. So the time complexity of this approach is O(2^{N} × **N**), which is fast enough for test set 1.

We need to approach the problem a bit differently for test set 2. We can start with observing the amount of walls we need to remove for a particular range of consecutive wall sections[i...j]. The most optimal way of making a set of consecutive wall sections have same height would be to figure out which height appeared the most, and remove all sections with a different height.

So for each consecutive set of walls, we can calculate number of wall removals needed. Let's say, R(i, j) defines number of removals necessary to have all wall sections from i to j have the same height.

We can define a solution based on a function F(x, k), where F(x, k) denotes the number of the walls we need to remove so that the sections from 1 to x
in the input has **A**_{i} ≠ **A**_{i+1} in at most k places.
We can define the recurrence relation as, F(x, k) = min(F(i, k-1) + R(i+1, x)) for all 1 ≤ i ≤ x-1.
The minimum number of walls that we need to remove for given **N** and **K** is F(**N**, **K**).
We can compute this function using dynamic programming, which will have O(**N**^{2} × **K**) time complexity, which is fast enough for test 2.

We can have a faster solution, if we decompose the problem from a slightly different angle. We can think about running binary search on number of removals needed to satisfy
the condition. In each iteration of binary search, we need to calculate if it is possible to have k or less number of positions where **A _{i}** ≠

Test Data

We recommend that you practice debugging solutions without looking at the test data.

We can solve this test set by considering all ordered pairs of employees. For an ordered pair
(i, j), we can check whether there is a skill that the i-th employee knows that the j-th employee
does not know with a simple O(**C _{i}** ×

This solution runs in O(5^{2} × **N**^{2}).

We can solve this test set by defining m(i) as the number of employees who can mentor the i-th employee. If we can compute m(i), the answer to the problem is the sum of all m(i).

To compute m(i), we can count the number of employees who **cannot** mentor the i-th employee
instead. We can observe that the j-th employee cannot mentor the i-th employee if and only if the
set of skills known by the j-th employee is a subset of the set of skills known by the i-th
employee. Therefore, we would like to count the number of employees whose set of skills is a
subset of the set of skills known by the i-th employee.

To count this, we can consider every subset of
{**A _{i1}**, ...,

To be able to compute the number of employees whose set of skills is exactly a given set, we can preprocess the set of skills into an occurences hashmap. In other words, we can keep a hashmap that takes a set of skills as its key and returns the number of employees who knows the exact same set of skills as its value.

For each employee i, we need to consider every subset of
{**A _{i1}**, ...,

Test Data

We recommend that you practice debugging solutions without looking at the test data.

Since there are very few villages for this set, we can calculate the sum of beauty values of illuminated villages for every possible set of villages we choose to build lighthouses in and then take the maximum among these.

For each such set, we have to find which villages will be illuminated. So, for each village, we see if it is in the set or if any of its neighbours are in the set and add its beauty value accordingly.

Since there will be 2^{V} such sets and for each such set we are taking O(**V**) time to figure out what is the corresponding total beauty value for the set, the overall complexity of this approach is O(**V**2^{V})

The the graph formed by taking the villages as nodes and roads as edges is a tree. Let's root this tree at node number 1.

Now, let us define a function maxBeauty(K, P, Q) which represents the maximum beauty value we can obtain from nodes in the subtree of node K (including itself) such that P is a boolean indicating whether the parent node of K has a lighthouse and Q is a boolean indicating whether K itself has a lighthouse. The solution to our problem is simply max(maxBeauty(1, 0, 1), maxBeauty(1, 0, 0)). We consider a few cases to evaluate maxBeauty(K, P, Q).

If Q = 1, then we have a lighthouse placed at K. Which means all of its children will be illuminated irrespective of them having a lighthouse or not. Therefore, in this case,

maxBeauty(K, P, Q) = **B**_{K} + sum of max(maxBeauty(C, 1, 0), maxBeauty(C, 1, 1)) for all children C of node K.

If Q = 0 and P = 1, then irrespective of whatever we choose for the children of K, they are not going to recieve light from K but K itself is going to be illuminated. Therefore, in this case,

maxBeauty(K, P, Q) = **B**_{K} + sum of max(maxBeauty(C, 0, 0), maxBeauty(C, 0, 1)) for all children C of node K.

Else, we have Q = 0 and P = 0. This means that the children of K are not going to recieve light from K but the illumination of K depends on whether we place a lighthouse in at least one of the children of K.

This case can be handled using a dynamic programming approach. We define dp[i][j] as maximum sum of beauty values of all illuminated nodes in the first i subtrees of node K such that, if j = 0 then we have not placed a lighthouse in any of the first i children of K and if j = 1 then there is at least one node among the first i children of K with a lighthouse.

Therefore, dp[i][0] = dp[i-1][0] + maxBeauty(C_{i}, 0, 0) and

dp[i][1] = max(dp[i - 1][1] + max(maxBeauty(C_{i}, 0, 0), maxBeauty(C_{i}, 0, 1)), dp[i - 1][0] + maxBeauty(C_{i}, 0, 1)).

(Here, C_{i} represents the ith child of K)

Finally, for this case, maxBeauty(K, P, Q) = max(dp[M][1] + **B**_{K}, dp[M][0]) where M is the total number of children of K.

Since for every node K we can get maxBeauty(K, P, Q) for all values of P and Q in O(M) time, overall complexity of this approach is O(**N**).

Test Data

We recommend that you practice debugging solutions without looking at the test data.