В Институте Морской Биологии открыли несколько новых видов глубоководных моллюсков, и теперь стараются понять их генеалогию. Для этого лаборант Петя извлёк некоторый конкретный участок генома у каждого вида моллюсков, а лаборант Вася построил $$$T$$$ предположительных частичных эволюционных деревьев на основе внешних признаков.

Частичные эволюционные деревья, построенные Васей, представляют из себя корневые деревья, в которых каждая вершина соответствует какому-то виду. Корень при этом соответствует общему прародителю, а листья — современным видам.

Для каждого вида учёные наблюдают один и тот же участок генома, который представляется в виде строки из символов A, G, C и T (каждый символ отображает один нуклеотид). Известно, что у всех видов этот участок имеет одну и ту же длину, но в процессе эволюции некоторые нуклеотиды могли замениться на другие (удалений и добавлений нуклеотидов без замены произойти не могло). При этом каждому из современных видов соответствует один из $$$G$$$ участков генома, извлечённых Петей, а участки генома видов-прародителей неизвестны.

Из предыдущих эмпирических наблюдений Пете и Васе известно, что эволюция — медленный процесс, и поэтому для каждого дерева, построенного Васей, они хотят определить его наименьший возможный вес. Весом эволюционного дерева при этом называется сумма весов рёбер этого дерева, а весом ребра — количество изменившихся нуклеотидов между видом-предком и видом-потомком.

Сами лаборанты не смогли решить такую задачу, поэтому просят Вас помочь им!