Streszczenie

Treść

Nowy webmaster Koła Naukowego Studentów Wydziału Informatyki ma ambitne plany. Za namową koleżanek i kolegów chce całkowicie zmienić wygląd stron internetowych Podlaskiego Turnieju w Programowaniu Zespołowym, a przy okazji dodać kilka ciekawych funkcjonalności. Jedną z nich jest możliwość publikowania przez internautów własnych artykułów na temat programowania i algorytmów. Oprócz wgrywania artykułów, każdy autor będzie miał możliwość wprowadzenia krótkiego streszczenia, które pojawi się na stronie głównej. Webmaster wie, że nie każdy będzie chciał z tej możliwości skorzystać i dlatego planuje zaprogramowanie modułu, który streszczenie będzie generował automatycznie, na podstawie kilku pierwszych zdań artykułu.

Webmaster chce, aby wszystkie streszczenia zajmowały możliwie jednakową ilość miejsca. W pierwszym odruchu chciał po prostu wycinać z początku artykułu z góry zadaną liczbę liter. Szybko się jednak zreflektował, że przecież każda litera ma inną szerokość. Dlatego też obliczył, w przybliżeniu, wymiary wszystkich liter i postanowił wycinać tekst do zadanej z góry sumarycznej szerokości liter. Po tej operacji nasz dzielny student przypomniał sobie, że nieelegancko byłoby przycinać tekst w połowie słowa. W związku z tym postanowił usuwać ze streszczenia początki niedokończonych słów i zbędne spacje z końca tak obrobionego tekstu.

Po wytężonym wysiłku intelektualnym webmastera rozbolała głowa i zadanie implementacji modułu generującego streszczenia powierzył Tobie, ponoć zdolnemu i dobrze zapowiadającemu się programiście. Napisz program, który dla podanego pełnego tekstu artykułu, maksymalnej szerokości streszczenia i szerokości pojedynczych liter wygeneruje streszczenie zgodnie z algorytmem wymyślonym przez webmastera.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

W pierwszym wierszu zestawu danych podany jest pełny tekst artykułu. Tekst składa się wyłącznie z małych liter alfabetu łacińskiego oraz znaków spacji. Artykuł zawsze składa się z co najmniej dwóch słów, a łączna jego długość nie przekracza 10 000 znaków. Ostatnim jego znakiem jest zawsze litera.

Drugi wiersz zestawu danych zawiera liczbę całkowitą s (10<=s<=50 000) oznaczającą zadaną szerokość streszczenia. Należy przyjąć, że szerokości poszczególnych znaków są następujące:

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest streszczenie wygenerowane zgodnie z algorytmem webmastera. Dane wejściowe są tak dobrane, że streszczenie zawsze składa się z co najmniej jednego słowa. W przypadku, gdy zadana szerokość streszczenia jest większa niż całkowita szerokość artykułu, jako wynik należy podać pełny jego tekst.

Przykład

dane wejściowe:
2
ala ma kota
14
ala ma  kota
35

wynik:
ala
ala ma