Frozen Archaeology
By Leandro Zatesko, UFFS 
Brazil
By Leandro Zatesko, UFFS Brazil
After undoing the malevolent Hans's malignant plan and saving the king of Arendelle, Elsa, Anna e Kristoff have started an archaeology project to know more about the prehistoric past of the continent on which nowadays Arendelle is located. During the excavations, they have discovered that the continent was actually formed geologically by the collision of four continents once separated. They have even been able to discover the names with which the peoples of that age used to call those continents: Westeros, Essos, Sothoryos and Ulthos. However, they are still in the process of identifying the families that used to inhabit the first continent, Westeros, since the promiscuity among the ancient peoples was very big and the records seem too confusing. At the present stage of the project, they are considering that the peoples were divided only in two large families: Stark and Lannister. In the future they intend to divide these families better. For instance, the goal is, given the genetic codes of the fossilised individuals, to classify the individuals in those two families in order to minimise the relations of kinship among individuals classified in different families.
More formally, we say that an individual X is relative of an individual Y if the genetic codes of both individuals share an identical contiguous part of length at least P% of the length of one of the codes — as all the individuals are humans, the genetic codes have always the same length. For example, take the individuals of codes GATAGACA and CATACAGA. If the kinship criterion P is set to 62, the individuals shall be considered relatives, since ACAGA is a contiguous part of both codes and has length 5 ≥ 8 × 62% (if you can't understand why ACAGA is a contiguous part of GATAGACA, understand that Elsa and her team consider genetic codes as circular strings). Yet, if P = 63, the individuals shall not be considered relative. This way, Arendelle researchers' goal is to classify the fossilised individuals in the families Stark and Lannister in order to minimise the number of bad pairs. We say that a pair (s, l) is bad if it satisfies the following three conditions:
Mandatorily, at least one individual must be classified as Stark and at least one as Lannister.
The first line of the input consists of two integers, N and P (2 ≤ N ≤ 50, 0 ≤ P ≤ 100), which represent respectively he number of individuals fossilised and the kinship criterion set. Each one of the N next lines consists of at most 104 characters in the set {A, T, C, G}, representing the genetic code of an individual. Except possibly for the first, the lines of the input have all the same number of characters.
Output a line containing only the least possible number of bad pairs in a classification of the individuals in the families.
| Input Sample | Output Sample |
|
2 62 |
1 |
|
2 63 |
0 |
|
5 50 |
2 |