Nosaukums
Burtu svītrošana (svitro)
Laika limits
1.00s
Atmiņas limits
256.0 MB

Definīcija

Dota simbolu virkne S, kuras garums ir N (0<=N<=100) un vārdnīca, kas satur M (0<=M<=100) vārdus. Katra vārda garums nepārsniedz N burtus. Gan virkne, gan vārdi sastāv no latīņu alfabēta mazajiem burtiem.

Uzrakstiet programmu, kas nosaka, kāds mazākais burtu skaits jāizsvītro no S, lai atlikušo virkni varētu izveidot pierakstot vienu otram galā vārdnīcas vārdus. Katra vārda izmantošanas reižu skaits nav ierobežots. Uzskatīsim, ka tukšo virkni var izteikt ar jebkādas vārdnīcas palīdzību.


Ievaddatu raksturojums

Ievaddatu pirmā rinda satur naturālus skaitļus N un M, kas atdalīti ar tukšumsimbolu. Faila otrajā rindā dota burtu virkne S. Nākošajās M faila rindās katrā dots pa vienam vārdnīcas vārdam.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada vesels skaitlis - mazākais burtu skaits, kāds jāizsvītro no S, lai atlikušo virkni varētu izveidot ar vārdnīcas vārdu palīdzību.


Piezīmes

Veids, kādā var svītrot burtus, lai atlikušo virkni varētu izveidot ar vārdnīcas palīdzību testpiemērā: abafchtdsya

Uzdevums izmantots Ukrainas XIV informātikas olimpiādē 2001.gadā.


Paraugdati

Stdin
11 5
abafchtdsya
aba
a
bach
dsy
zero
Stdout
2

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.