 7

# Morty and his array

Difficulty: HARD Contributed By

Problem Statement

#### Example : let ‘arr’ = [1,0,0] then the possible sub-arrays of ‘arr’ will be- {1}, {0}, {0}, {1,0}, {0,0}, {1,0,0}.

##### For Example
``````Let Arr[] = {1, 1, 1, 4, 1, 2, 4}, K=2

The given array can be split into two sub-arrays {1, 1, 1, 4}, {1, 2, 4}. The total cost will be for the first sub-array - 2+ 3(frequency of 1 is 3 in the first sub-array) + for the second sub-array - 2, Hence total cost is 7.
``````
##### Input Format :
``````The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains two integers, ‘N’ and ‘K’, denoting the length of the array and cost of each subarray, respectively.

The second line of the test case contains an array ‘Arr’ of ‘N’ integers.
``````
##### Output Format :
``````For each test case, print a single integer ‘ANS’ representing the minimum cost of splitting the array.

Output for each test case will be printed in a separate line.
``````
##### Note :
``````You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
``````
##### Constraints :
``````1 <= T <= 10
1 <= N <= 500
1 <= K <= 500
1 <= Arr[i] <= 500

Time limit: 1 sec
``````
##### Sample Input 1 :
``````2
7 2
1 1 1 4 1 2 4
5 3
1 2 3 3 5
``````
##### Sample Output 1 :
``````7
5
``````
##### Explanation For Sample Output 1 :
``````For the first test case, we can divide the array into two subarrays {1, 1, 1, 4} and {1, 2, 4} so the answer will be 7.

For the second test case, we have to keep the whole array to minimize the cost, so the answer will be the cost of 1 subarray i.e. 3, plus the frequency of non-unique numbers i.e. 2.
``````
##### Sample Input 2 :
``````2
11 5
1 5 1 1 1 1 7 5 1 2 4
7 3
1 2 3 2 1 2 3
``````
##### Sample Output 2 :
``````13
8
``````   Console