Рабочее место участника

Reconstructing the evolutionary relationships among species is one of major subjects in biology. Typically, each species is presented by a sequence over four nucleotide types: A, C, G, and T. A nucleotide mutation is said to be happened at position `i` between two sequences `X\ =\ (x_1,\ …,\ x_l)` and `Y\ =\ (y_1,\ …,\ y_l)` if `x_i\ ≠\ y_i`. The distance between two sequences `X` and `Y` is calculated as the total number of nucleotide mutations between them.

There are `n` contemporary species, which are labeled from 0 to `n-1`. The evolutionary relationships among species are depicted by a binary rooted tree where `n` leaves represent `n` contemporary species, internal nodes represent ancestor species, and branch lengths represent distances between species (see figure below). This tree can be represented in text form using brackets as ((0,1),((3,4),2)).

Since nucleotide sequences are not available for ancestor species, our task is to determine one nucleotide sequence for each ancestor species such that the tree length (total branch lengths) is minimized.

The first line containing two integers `n` and `l` (`n\ ≤\ 1000`, `l\ ≤\ 100`) indicating the number of contemporary species and the length of nucleotide sequences, respectively. The `i`-th line of the following `n` lines contains the nucleotide sequence of the contemporary species labeled `i-1`. The last line contains the text representation of the tree topology.

Write an integer number indicating the minimum length of the tree.

2 3
AGG
CGT
(0,1)

2

5 5
ACGTG
ACATG
CTATG
ATATG
GTATT
((0,1),(2,(3,4)))

5