Challenge 24 Electronic Contest Practice

Settlers of different planets have distinct words for the same notions because of the millennia spent in isolation. For example they call a "Big Mac" "Bug Mac" on Betelgeuse (owing to the gourmet insects indigenous to the planet). Recently however the appearance of affordable FTL communication devices enabled etymologists to collect and analyse large corpora of planetary variations.

The need arose for a tool to help map the spread and development of word variations. Usually etymologists have an idea about how the settlers moved from planet to planet, and this spread of human civilization can be represented by a binary tree. The leaves represent the current colonies, while other nodes are past versions of these colonies or abandoned colonies or colonization hiveships. The input for the tool consists of this binary tree as assembled by the researchers and the different variations of a word for every current colony.

The distance in etymological terms between two words is the number of letters that are not the same in the two words (e.g. D("Big Mac","Bug Mac") = 1). It is only defined for words of the same length, and the input is preprocessed so that all variations are the same length. Each node (whatever it represents) has a version of the word in analysis associated with it, but it is only known for the leaves of the tree. This means that every edge in the tree can be associated with the distance between the words of the two nodes connected by it. Depending on the word variations in the non-leaf nodes the sum of the distances in the tree can be different. The output of the tool has to be the minimal total distance. This is useful for the etymologists for evaluating migration models and the actual word variations will only have to be enumerated by a later version.

Input:

A leaf node is represented with the word variation used on the colony between quotation marks: "Bug Mac"
A non-leaf node is represented with the two child nodes between parenthesis and separated by a comma: ("Bug Mac","Big Mac")

Output:

The output is simply a number (in decimal representation).

This is the electronic variant of the problem. Read more here about submitting solutions!

Example

Input:
(("alma","alba"),"alap")
Output:
3