1. You are given a number N representing number of words. 2. You are given N space separated strings(i.e. words). 3. You are given a number W representing width of sentence (maxmimum characters a line can hold). 4. You are allowed to append extra spaces only at the end of words. 5. Cost of word-wrap = (e1*e1*e1) + (e2*e2*e2) + (e3*e3*e3) + .... where e1,e2,e3 ... en are extra-spaces at the end of line 1,line 2,line 3 .... line n(respectively). (view image to get more clear insight of question). 6. Find the MINIMUM COST of optimal word-wrapping method.
Input Format
A number N (representing "NUMBER OF WORDS"). str1 ,str2 ,str3 ,str4 .... strn (N space separated strings). A number W (representing "WIDTH OF LINE").
Output Format
Find minimum cost of word-wrapping. Check the sample output and question video.
Constraints
1 <= N <= 10 1 <= len(str) <= 15 MAXIMUM LENGTH(str) <= W
Example
Input
4 aaa bb cc aaaaa 6
Output
29