Minimizing Relative Path Lengths

Bessie the cow stores all her files in a directory tree rooted at a directory named bessie. Each file is stored in a directory (possibly directly in bessie), and its location is described by an absolute path such as bessie/folder1/folder2/file.

From any directory that Bessie chooses to stand in, each file is referenced by a relative path. In a relative path, the symbol .. refers to the parent directory. For example, if Bessie is in directory folder2 in the tree below:

bessie/
  folder1/
    file1
    folder2/
      file2
  folder3/
    file3
  file4

Then the four files can be referenced as:

../file1
file2
../../folder3/file3
../../file4

Bessie would like to choose a directory from which the sum of the lengths of the relative paths to all files is minimized. The length of a relative path is simply the total number of characters (letters, digits, punctuation such as '/', or the dots in ..).

Note: When moving from a directory to its parent, the relative path component .. is always followed by a slash (i.e. ../) except possibly at the very end if no further characters follow. For the sake of this problem, you can assume that every .. is counted as three characters (two dots and a slash), and every directory name when used in a path is followed by a slash. For example, from directory folder1, a file file1 in that same directory has path file1 (its length is the length of file1 only), while a file in a subdirectory would be referenced with subdir/file, whose length is (len(subdir) + 1 + len(file)).

Given a list of n files with their absolute paths (each beginning with bessie/), determine the minimum possible sum of the lengths of the relative paths to all files, if Bessie may choose any directory in the file tree from which to reference all files.

Hint: When you change your working directory, the relative cost for files in the subtree of the new directory decreases (as you don’t need to include that directory's name and slash), but for files outside that subtree the cost increases by three per file (since you need to add a ../ for each step upward).

The formula when moving from a parent directory to a child directory u is given by:

$$new\_cost = parent\_cost - (\text{len}(u)+1) \times count(u) + 3 \times (total\_files - count(u))$$

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of files. Each of the next n lines contains a string representing the absolute path to a file. Each path:

• Starts with bessie and uses '/' as a separator.
• Contains only letters, digits, or underscores in file or directory names.

Directories that are not explicitly listed are implied by the file paths.

outputFormat

Output a single integer, the minimum total sum of the lengths of the relative paths to all files if Bessie chooses the optimal directory to stand in.

sample

4
bessie/folder1/file1
bessie/folder1/folder2/file2
bessie/folder3/file3
bessie/file4

42