FONTSIZE - Font Size

Description

John bought a billboard. He knows what text he wants to put on it, and he has chosen a monospace font to use, but he doesn't know what the font size should be.
Naturally, John wants to use the largest font size possible.
Sizing works as follows:
  • The height of a line is the font size.
  • The width of a character is two-thirds of the font size.
  • Lines can only break between the space-separated words.
  • If a space ever falls at the beginning or end of a line, it is omitted.
Don't worry about details like kerning and line spacing.
For example, consider the message "The lazy brown dog".
On a billboard 60 inches wide and 25 inches tall, the maximum font size is 10 inches:
The lazy
brown dog
On a billboard 50 inches wide and 50 inches tall, the maximum size is 12.5 inches:
The
lazy
brown
dog
Given the size of the billboard and the message, find the largest font size that will allow the entire message to fix.

Input

The first line is the width of the billboard in inches, 0 <= W <= 7500, and the height of the billboard in inches, 0 <= H <= 7500.
The third line is the non-empty message, which is comprised of alphanumeric words separated by single spaces. The message is most 10,000 characters long.

Output

Print the maximum possible font size, in inches. Your answer must be accurate to within 0.001 of the actual value.
Input Input
60 25
The lazy brown dog
50 50
The lazy brown dog
Output Output
10
12.5

Added by:BYU Admin
Date:2014-02-23
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.