Био једном један филм. Ви стојите испред биоскопа и питали сте \(N\) људи да вам испричају једну сцену из филма. Како су пуком коинциденцијом сви ти људи такође одлични програмери као и ви, свако од њих вам је испричао једну сцену, представљену као стринг малих слова енглеске абецеде, уз напомену да се та сцена јавља у филму тачно једном. Ваш задатак је да реконструишете филм, тачније, да пронађете стринг \(S\) најкраће могуће дужине који ће сваку сцену садржати тачно једном, такав да се тај стринг састоји само од првих \(K\) малих слова енглеске абецеде.

Описи функција

Потребно је да имплементирате функцију

• \(Resi(N, K, L[\ldots], A[\ldots][\ldots], S[\ldots])\)

која треба да нађе стринг описан у тексту задатка. \(N\) означава број људи који су вам рекли једну сцену из филма. \(K\) је број који означава колико првих малих слова енглеске абецеде можете користити за конструисање филма. \(L\) је низ дужине \(N\) који садржи дужине датих сцена. \(A\) је низ низова, где елементи \(A[i][1], \ldots, A[i][L[i]]\) чине \(i\)-ту сцену. Сви ови елементи су мала слова енглеске абецеде. Уколико такав стринг постоји, пронађени стринг минималне дужине сместите у низ \(S\) почев од позиције \(1\), а његову дужину вратите као резултат функције. Уколико такав стринг не постоји, довољно је да из функције вратите број \(-1\). Гарантује се да ће за стринг \(S\) бити резервисано довољно меморије да цео резултујући стринг може да стане. Сви низови су индексирани од 1.

Примери

Пример 1

Нека је \(N=6, K=26\), а стрингови су ave, venge, ger, rs, r, av. Решење је стринг avengers. Ваша функција треба да упише овај стринг на позиције \(S[1], \ldots, S[8]\) и да врати број \(8\).

Пример 2

Нека је \(N=2, K=2\), а стрингови су ababa, aba. Решење не постоји. У овом случају довољно је да ваша функција врати број \(-1\).

Ограничења

• \(1 \leq N \leq 14\)
• \(1 \leq K \leq 26\)
• \(L_i \geq 1\)
• \(\sum_{i=1}^N L_i \leq 150\)

Подзадаци

• Подзадатак 1 [14 поена]: \(K = 2\), уколико решење постоји, тада је оно не дуже од \(18\).
• Подзадатак 2 [12 поена]: \(N = 2\)
• Подзадатак 3 [23 поена]: \(N = 3\)
• Подзадатак 4 [51 поен]: Без додатних ограничења.

Детаљи имплементације

Потребно је да пошаљете тачно један фајл film.cpp, који имплементира поменуту функцију. Осим тражене функције, ваш фајл може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке.

Ваша функција мора бити следећег облика:

int Resi(int N, int K, int* L, char** A, char* S);

Вашим програмима је дозвољено да мењају садржај низова/матрица, али не смеју да приступају ван граница датих низова.

Тестирање и експериментисање

Уз задатак, обезбеђен вам је “template” фајл code.cpp који можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp који служи да лакше тестирате кодове. Овај програм учитава са стандардног улаза следеће податке:

• У првом реду бројеве \(N, K\),
• У наредних \(N\) редова по један стринг - \(A_i\).

Затим овај програм зове вашу функцију. Нека је ваша функција вратила број \(X\). Уколико је \(X < 0\), штампа се само \(X\). У супротном, штампа се \(X\) и првих \(X\) карактера низа \(S\). Кодове ових програма можете мењати по потреби.