Background

Typical slide presentation programs such as OpenOffice Impress, Kpresenter or PowerPoint are able to fit the text that the user writes into slides by changing the size of the font used for the text, so that the entire text can fit into the slide.

Those programs start using a font with a typical font size (measured in points). When the text typed by the user does not fit into the slide, they try to use a smaller font (less size in points) to fit the text into the slide.

Thus, presentation programs must apply an algorithm to calculate the bigger font size that allows the typed text to fit into the slide.

The Problem

You have to write a program to solve this problem. Given a set of paragraphs that have to be written into a slide, you have to calculate the maximum font size in points that allows all the text to fit into the slide.

There are some additional rules to consider: all characters (including spaces) have the same size in points, PxP, where P is the selected font size in points. Font sizes can vary from 8 to 28 points. If a paragraph cannot be fit into one line, wrapping can occur, but only at word boundaries (i.e., after one space). Thus, a paragraph can use several horizontal lines.

The Input

The input begins with a line with an integer N indicating the number of slides. Each slide starts with a number M, indicating the number of paragraphs of this slide. Then, M lines of text follow, one for each paragraph. And finally a line with two integers (X and Y), indicating the size of the slide in points. There will not be more than one space between words, and neither empty paragraphs. You can also assume that there are not spaces at the beginning or at the end of a paragraph.

The Output

The output will consist of N lines (one for each slide). Each line will be either "No solution" (if the text cannot be fit with any point size between 8 and 28), or P, the maximum size of the font in points that allows the slide to fit the paragraphs.

Sample Input

3
3
En un lugar de la mancha
de cuyo nombre no quiero acordarme
no ha mucho que vivia...
375 35
1
LE LO
40 40
2
I love this hyper-mega-cosmic-contest.
The winner.
100 80

Sample Output

11
20
No solution

 
#include <iostream>
#include <sstream>
using namespace std;

int main() {
    int t, n, X, Y;
    cin >> t;
    while(t--) {
        cin >> n;
        cin.ignore(100, '\n');
        string p[100][100], in;
        int pw[100] = {};
        for(int i = 0; i < n; i++) {
            getline(cin, in);
            stringstream sin;
            sin << in;
            while(sin >> p[i][pw[i]])
                pw[i]++;
        }
        cin >> Y >> X;
        int font, i, j;
        for(font = 28; font >= 8; font--) {
            if(font*n > X)  continue;
            int x = 0, y = 0;
            int first;
            for(i = 0; i < n; i++) {
                x += font, y = 0;
                first = 0;
                for(j = 0; j < pw[i]; j++) {
                    if(y+font*(p[i][j].length()+first) > Y) {
                        x += font, y = font*p[i][j].length();
                    } else {
                        y += font*(p[i][j].length()+first);
                    }
                    if(y > Y || x > X) {
                        x = X+1;
                        break;
                    }
                    first = 1; // space
                }
            }
            if(x <= X) {
                cout << font << endl;
                break;
            }
        }
        if(font == 7)
            cout << "No solution" << endl;
    }
    return 0;
}