Била једном једна бесконачна усмерена права линија. Она је била поплочана стринговима који су сви били исти, исто оријентисани (у истом смеру као права) и били су једнаки стрингу \(A\). Међутим, бесконачно (и то непребројиво) много пацова је напало праву и појело све плочице, па је сад остала само гола права. Ви на располагању имате бесконачно (али пребројиво) много копија сваког од \(M\) врста стрингова, којима треба поплочати ову праву. Ваш задатак је поплочате праву тако да она изгледа исто као раније. Обратите пажњу на то да ова права нема ни почетак ни крај нити су позиције на правој индексиране на било који начин (видети примере за објашњење). Како бисте мајсторима олакшали посао, ваш задатак је да направите једну плочицу конкатенацијом (надовезивањем) неких од датих стрингова, тако да се том једном плочицом може извршити поплочавање. Није дозвољено окретати ове стрингове (а ни целу плочицу) наопачке. Помозите мајсторима тако што ћете им рећи колико је најмање стрингова потребно да се направи плочица којом може да се поправи штета коју су нанели пацови. Уколико ово није могуће, ваш одговор треба да буде број \(-1\) (омиљени број сваког пацова).

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

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

• \(Resi(N, А[\ldots], M, L[\ldots], B[\ldots][\ldots])\)

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

Примери

Пример 1

Нека је \(A = baabaa, B = \{a, b, c\}\). Могуће је формирати плочицу \(aba\) помоћу два стринга \(a\) и једног стринга \(b\). Овом плочицом добија се поплочавање које је једнако поплочавању које се добија стрингом \(baabaa\):

...baabaabaabaa...
.....abaabaabaaba...

Решење овог примера је \(3\), јер смо за формирање плочице \(aba\) искористили \(3\) стринга.

Пример 2

Нека је \(A = bca, B = \{ab, bc, ca\}\). Могуће је формирати плочицу \(abcabc\) редом помоћу стрингова \(ab, ca, bc\). Лако се уочава да се и овом плочицом добија поплочавање једнако поплочавању стрингом \(bca\):

...bcabcabcabca...
.....abcabcabcabc...

Ограничења

• \(N \leq 500\)
• \(M \leq 100.000\)
• \(1 \leq L_i \leq N\)
• \(\sum_{i=1}^{M} L_i \leq 1.000.000\)
• Сви стрингови се састоје само од малих слова енглеске абецеде

Подзадаци

• Подзадатак 1 [4 поена]: Стринг \(A\) садржи само слова \(a\).
• Подзадатак 2 [33 поена]: \(N, M \leq 100\).
• Подзадатак 3 [11 поена]: \(M \leq 1000\).
• Подзадатак 4 [52 поена]: Нема додатних ограничења.

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

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

У зависности од програмског језика који користите, ваша функција мора бити следећег облика:

За Pascal, NizStringova је тип који је дефинисан као Array of Array of Char. Вашим програмима је дозвољено да мењају садржај низова/матрица, али не смеју да приступају ван граница датих низова.

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

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

• У првом реду стринг \(A\),
• У наредном реду број \(M\)
• У наредних \(M\) редова по један стринг, \(B_i\).

Затим овај програм зове вашу функцију и штампа њен резултат. Кодове ових програма можете мењати по потреби.