 1

# Word Wrap

Difficulty: EASY
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.
``````
##### 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
`````` Want to solve this problem? Login now to get access to solve the problems