Fişierul intrare/ieşire:	palsubsecv.in, palsubsecv.out	Sursă	Concursul National de Informatica "Adolescent Grigore Moisil"
Autor	Florin Chirica	Adăugată de	AGMInformatica •AGMinformatica
Timp execuţie pe test	0.4 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	5/5

Vezi solutiile trimise | Statistici

Palsubsecv

Se da un sir de caractere S de lungime N. Trebuie sa gasim subsirul palindromic al lui S de lungime maxima, cu lungime para.
Avem un buget de B dolarei. Odata ce alegem o solutie, va trebui sa tinem cont de R restrictii care ne vor scadea din buget.
O restrictie de forma (a, b, c) inseamna ca daca este luata subsecventa dintre a si b in palindrom, trebuie sa platim c dolarei. Asta inseamna ca, fiind alese toate pozitiile dintre a si b in palindromul solutie, trebuie sa platim c dolarei.
Care este palindromul par de lungime maxima astfel incat la final sa ramanem cu un numar nenegativ de dolarei?

Date de intrare

Fişierul de intrare palsubsecv.in va contine pe prima linie T, numarul de teste. Pe prima linie a fiecarui test se vor afla trei numere intregi N, R si B, separate prin cate un spatiu. A doua linie va contine sirul S. Urmatoarele R linii ale unui test vor contine fiecare cate trei numere intregi a, b si c, separate prin cate un spatiu, cu semnificatia din enunt.

Date de ieşire

În fişierul de ieşire palsubsecv.out se vor afla T linii, pe fiecare cate un numar natural care va reprezenta raspunsul la cerinta.

Restricţii

• 1 ≤ T ≤ 15
• 1 ≤ N ≤ 33
• 1 ≤ R ≤ N²
• 1 ≤ B ≤ 10⁹
• 1 ≤ a ≤ b ≤ N
• 1 ≤ c ≤ 10⁵
• S contine doar litere mici ale alfabetului englez
• x e nenegativ daca x ≥ 0

Exemplu

Explicaţie

In primul exemplu, ori luam subsirul aa ori bb. Nu putem sa le luam pe ambele, deoarece ar trebui sa platim 11 dolarei din cauza ca luam toate caracterele din intervalul [4, 5].

Cum se trimit solutii?