Компоновка стикеров
Текст на стикере состоит из слов, содержащих прописные и заглавные латинские буквы. Слова разделены пробелами, переводами строки и следующими знаками пунктуации: ",", ".", "!", "?".
Перед словами и за ними может находиться произвольное число пробелов и пустых строк, но не более одного знака пунктуации после каждого слова. Стикер печатается моноширинным шрифтом, то есть каждый символ занимает на бумаге прямоугольник фиксированного размера. Стикер представляет собой наименьший прямоугольник, окаймляющий текст, плюс поле шириной в один символ.
Будут напечатаны много копий стикеров, поэтому необходимо минимизировать количество использованной бумаги. Стикер необходимо сделать так, чтобы он занимал как можно меньше площади. Например, рассмотрим стикер со следующим текстом:
Our pink elephants have great size and a small price. Buy our elephants!
Если текст вывести в одной строке, то его площадь будет равна (72 + 2) * (1 + 2) = 222 символов. С другой стороны, если вывести текст следующим образом:
то достаточно использовать только (18 + 2) * (4 + 2) = 120 символов.
Ваша задача - разбить текст стикера на несколько строк таким образом, чтобы он занимал наименьшую площадь. Перевод строки можно вставлять после любого слова или знака пунктуации. Один пробел должен отделять каждое слово от предыдущего слова или знака пунктуации в одной строке. Остальные пробелы и символы перевода строки сохранять не обязательно.
Входные данные
Входные данные состоят из одного или нескольких строк текста стикера. Текст содержит только следующие символы: "A" до "Z", "a" до "z", ",", ".", "!", "?", пробелы и переводы строки. Длина текста не более 10000 символов. Текст всегда содержит символы, не являющиеся пробелами, и начинается всегда с буквы.
Выходные данные
Вывести одно целое число — площадь наименьшего стикера.