TREEBA - Hackers

no tags 

 

Hakeri prisluškuju komunikaciju Mirka i Slavka te pokušavaju razumjeti presretnute poruke. Rječnik Mirka i Slavka sadrži M riječi te se svaka poruka koju jedan od njih pošalje drugome sastoji od niza riječi iz rječnika odvojenih razmacima. Međutim, poruke koje hakeri presreću su zbog slabe kvalitete njihove opreme izmjenjene na sljedeći način:
1. U poruku je umetnuto najviše K šumova – proizvoljnih nizova slova. Svaki šum je uvijek umetnut između dvije riječi ili prije prve ili nakon zadnje riječi, dakle nikad unutar neke riječi.
2. Svi razmaci između riječi u poruci su izbrisani.
Na primjer ako Mirko pošalje poruku 'mirko slavko', kada je hakeri presretnu ona može biti 'mirkoxyzslavko', gdje je niz 'xyz' šum, a riječi 'mirko' i 'slavko' se nalaze u rječniku. Hakerima je poznat njihov rječnik te su upravo zaprimili novu izmjenjenu poruku koju žele rastaviti na riječi iz riječnika i šumove. Od svih mogućih načina na koji se to može napraviti zanima ih onaj gdje ima najviše moguće riječi iz rječnika. Napišite program koji za zadani rječnik, zadani broj K, te zaprimljenu izmjenjenu poruku dobivenu na opisani način, određuje koliko najviše može biti riječi iz rječnika u rastavu, te određuje jedan (bilo koji) rastav u kojem je najviše moguće riječi iz rječnika.

Hackers are eavesdropping communication beetwen Mirko and Slavko and trying to understand the intercepted messages.

Dictionary from Mirko and Slavko contains M words and every message which one of them send to another consists of a series of words from dictionary separated by spaces.

However, the messages which hackers are intercepting due to poor quality of their equipment are changed as follows:

  1. In the message are inserted at most K noises - arbitrary strings of letters. Every noise is always inserted between two words or before the first or after the last word and never within a word. 
  2. All spaces between the words in the message are deleted. 

For example, if Mirko sends a message 'mirko slavko', when hackers intercept it, it can be 'mirkoxyzslavko', where 'xyz' is a noise, and the words 'mirko' and 'slavko' are found in the dictionary.

Hackers know their dictionary and have just received a new altered message which they want to disassemble to the dictionary words and sounds. Of all possible ways in which they can do that, they are interested in the one which has the most words from the dictionary.

Write a program that, given the dictionary, the number K, and received a modified message obtained as described above, determines a way in which the most words from dictionary are used.

 

Input

The first line contains number T ( 1 ≤ T ≤ 12 ) - the number of test cases.

The second line contains two integers M (1 ≤ M ≤ 1000) and K (0 ≤ K ≤ 10) - the number of words in the dictionary and the maximum amount of noise in each received message. 

The third line is the text messages received - a series of lowercase letters of length N (1 ≤ N ≤ 10 000). Each of the following M lines contains a word in the dictionary - a series of at least one and a maximum of 20 lowercase letters.

Output

In the first line of output write maximum number of words from the dictionary in disassembled message.

Example

Input:
1
5 3 
prisluskujuabcdnassumhakeri 
mirko 
nas 
slavko 
hakeri 
prisluskuju
Output:
3

Explanation: One of the messages is 'prisluskuju #### nas ### hakeri' which has two noises, and maximum of three words.


hide comments
paroaro: 2018-03-23 10:17:35

Šta si se stiso ko neka treeeeeeeeeeeeeeeeeeeeeeeeeeeba?


Added by:Ivan Šego
Date:2013-09-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Modified task from Croatian regional competition 2013