11

# Word Wrap

Difficulty: MEDIUM
Avg. time to solve
20 min
Success Rate
75%

Problem Statement
Suggest Edit

#### Your task is to form this arrangement with the minimum cost possible and return the minimum total cost.

##### Note:
``````1. Length of each word should be less than or equal to ‘M’.
2. You can’t break a word, i.e. the entire word should come in the same line and it must not be the case that a part of it comes in the first line and another part on the next line.
``````
##### Input Format:
``````The first line of the input contains an integer ‘T’ denoting the number of test cases.

The first line of each Test case should contain two positive integers, ‘N’ and ‘M’, where ‘N’ is the number of words and ‘M’ is the number of characters we require in each line.

Following ‘N’ lines, contains one word each.
``````
##### Output Format:
``````The only line of output of each test case should contain an integer denoting the minimum cost required to form the arrangement.

Print the output of each test case in a separate line.
``````
##### Note :
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 100
1 <= N <= 300
1 <= |words[i]| <= 100
1 <= M <= 100

Time Limit: 1sec
``````
##### Sample Input 1:
``````1
3 6
ab
a
b
``````
##### Sample Output 1:
``````0
``````
##### Explanation for sample input 1:
``````All the 3 words can be inserted in a single line.
ab a b Total Characters = 6
Hence extra spaces used are (6-6)^3=0
``````
##### Sample Input 2:
``````1
4 5
a
bc
def
ghij
``````
##### Sample Output 2:
``````10
``````
##### Explanation for sample input 2:
``````The optimal output will be:
a bc
def
ghij
Hence extra spaces will be -> (1)^3 + (2)^3 + (1)^3 = 10
``````
Console