Задача A. Сколько программ? ≡

Условие

Женя любит программировать! Она уже выучила N конструкций! Жене интересно, сколько программ заданной длины L она может составить из этих конструкций. Помогите ей сосчитать программы!

Женя игнорирует все пробелы и пустые строки в программе, и обращает внимание только на непробельные символы. Кроме того, Женя считает различными две программы, если они равны как строки, но для их создания были использованы различные последовательности конструкций.

Женя не требует, чтобы полученная программа компилировалась. Про компиляторы она еще не прочитала.

Формат входного файла

В первой строке входного файла содержится количество конструкций N, которые Женя уже выучила. Последующие N строк содержат сами конструкции. Длина никакой из конструкций не превосходит 255 символов. Если одна и та же конструкция встречается несколько раз, то её вхождения считаются различными, таким образом, Женя всегда рассматривает N различных конструкций.

Все строки содержат только символы с ASCII-кодами от 32 до 126. Кроме того, Женя хочет, чтобы пробелы в строках игнорировались (все остальные символы учитываются при подсчете длины).

В последней строке входного файла содержится число L.

Формат выходного файла

Ограничения

Примеры тестов

3
begin
clrscr
end
17

20

Задача C. Небольшая подтасовка ≡

Условие

В Динарии у власти находится жестокая партия Либеративов. Но оппозиционные настроения усиливаются, поэтому Либеративы решили перераспределить округа для голосования таким образом, чтобы оппозиционно настроенные кварталы присутствовали в как можно меньшем числе округов. Так как честная партия Консервалов не может допустить такого печального конца демократии в Динарии, Вам поручено найти способ нарушить планы Либеративов.

По новому плану столица будет разделена прямоугольной сеткой, в качестве сторон которой будут выбраны главные улицы и авеню. Все улицы и авеню проходят через весь город, имеющий форму прямоугольника, параллельно его сторонам (улицы — вертикально, а авеню — горизонтально). Нумерация начинается с левого нижнего угла. Город ограничивают четыре дороги: 1-я улица (левая граница), 100-я улица (правая граница), 1-я авеню (нижняя граница), 100-я авеню (верхняя граница). Очевидно, что эти дороги должны ограничивать округа, однако, не все дороги по плану будут являться границами округов. Кроме того, для соблюдения видимости честности Либеративы будут определять только вертикальные границы округов, в этом и заключается Ваш шанс, т.к. они вынуждены позволить Консервалам определять горизонтальные.

Вам известно местоположение всех оппозицонных кварталов, которые подавляющим большинством проголосуют за Консервалов. Квартал — это ровно один квадрат между соседними улицами и авеню (т.е. прямоугольник, не содержащий внутри никаких дорог). Вам стали известны планы Либеративов по расположению вертикальных границ. Расположите горизонтальные границы таким образом, чтобы оказалось как можно больше округов, в которых присутствует оппозиционный квартал.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

2
49 49 
50 50
2 1 100
3

3 1 50 100

Problem D. Multiplication puzzle ≡

Statement

The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the move player takes one card out of the row and scores the number of points equal to the product of the number on the card taken and the numbers on the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the final move, only two cards are left in the row.

The goal is to take cards in such order as to minimize the total number of scored points.

For example, if cards in the row contain numbers 10 1 50 20 5, player might take a card with 1, then 20 and 50, scoring 10*1*50 + 50*20*5 + 10*50*5 = 500+5000+2500 = 8000

If he would take the cards in the opposite order, i.e. 50, then 20, then 1, the score would be 1*50*20 + 1*20*5 + 10*1*5 = 1000+100+50 = 1150.

Input file format

Output file format

Constraints

Sample tests

6
10 1 50 50 20 5

3650

Problem P. Holey cloth ≡

Statement

Several pieces of cloth are laid out on the table without overlapping each other. These pieces contain many holes, some so big that entire other piece of cloth may fit into them. Digital black-and-white image of the tabletop was taken, on which areas covered by cloth are represented with '*'s and not covered areas with '.'s. A single piece of cloth is thus represented with 4-connected area of '*'s - i.e., a group of '.'s located next to each other horizontally or vertically, but not diagonally. For example, on the following image there are three pieces - one without holes, and two with one hole each - first has area of 8, and the second - area of 12.

.***..***
.*.*.**.*
.***.*.**
*...**.*.

Your goal is to find the piece with the most holes in it. The hole is a 4- connected area of '.'s completely surrounded with '*'s. If several pieces have the same number of holes, you must select the one with the smallest area.

Input file format

Output file format

Constraints

Sample tests

9 5
.********
.*......*
.*..**..*
.*......*
.********

22

Problem Q. Compacting stickers ≡

Statement

The text on a sticker consists of words formed from small and capital Latin letters. Words are separated by spaces, line breaks, and/or the following punctuation marks: ",", ".", "!", "?".

There may be any number of spaces and empty lines before and after the words, but there is no more than one punctuation mark after each word. Sticker is printed with monospace font, so every character occupies on the paper a rectangular area of fixed size. Sticker itself is a minimal rectangle enclosing the text plus a margin of one character in width.

Many copies of the sticker are to be printed, and to minimize paper consumption the sticker should be made as small in area as possible. Consider, for example, the sticker with the following text:

Our pink elephants have great size and a small price. Buy our elephants!

Printed in one line, this sticker will have an area of (72 + 2) * (1 + 2) = 222 characters. On the other hand, if printed in four lines, like this:

the sticker will only require (18 + 2) * (4 + 2) = 120 characters.

You objective is, given the text of a sticker, to break it into lines so as to achieve the smallest possible area for it. Line break may be inserted after any word or punctuation mark, but not before a punctuation mark. One space must separate each word from the preceding word or punctuation on the same line. You do not have to preserve other spaces or line breaks in the input file.

Input file format

Output file format

Constraints

Sample tests

Our pink
Elephants
have great size and a
small price .
Buy our elephants !
  

120