Space tourism has gained unprecedented popularity in recent years. There
are lots of people wishing to look closely at a triple star, walk on
the surface of a small asteroid or plunge into the depths of a gas
giant. Passenger ships began to fly between all popular star sectors. But
there is a little problem—a flight to a place of interest may take
several weeks, and you need to escape the boredom somehow, because
even a view out of the observation window doesn't change very often.
That's why many people now take a great interest in reading visual novels.
A visual novel is one of the attempts to rethink the conventional literature which
became possible after the mass transfer of books to electronic devices. The main
difference of the visual novel from an usual book is that its plot
can branch out, and after a few pages the reader may have
more than one option of choosing which page is next. The moments when
the reader has to make choices are called branches.
Many readers like to explore the entire novel, reading all possible
scenarios. After reaching one of the possible endings, they return to the beginning
of the story and try other plot variants. You, as the author of the novel “The
song of Asya”, want to make life of such readers easier.
First, after reading several endings the reader forgets for
what choices he has already explored all possible ways of further plot
development. So you have decided that the story should not offer options
which lead the reader to the fully explored chains of events. Secondly,
you have decided to add a button, which skips all the intermediate pages
of a story to the nearest branch or the finale. If you accidentally
press this button on a branch page, then nothing happens.
You have written all the chains of choices, leading to all the possible endings, and you
want to assess the total number of button clicks needed to choose the plot lines
and skip the unambiguous choices, which the reader needs in the best case to read the entire novel in all its versions.
The first line contains an integer n that is an amount of different endings of the story (1 ≤ n ≤ 105).
The i'th from the following n lines contains a non-empty line of lowercase Latin letters, describing all choices of the plot on the way to the i'th ending.
It is guaranteed that none of the lines is a prefix of the other line.
The total length of lines does not exceed 105.
Output the minimum amount of button clicks necessary to read all the possible variants of the plot.
If we denote the choice button clicks with Latin letters, and
the skip branch button clicks with the “*” symbol,
then one of the optimal strategies is “b*c*”.
Problem Author: Denis Dublennykh (prepared by Alexander Fetisov)
Problem Source: Ural Championship 2012