Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2442
Simple prefix compression

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Many databases store the data in the character fields (and especially indices) using prefix compression. This technique compresses a sequence of strings A1, ..., AN by the following method: if there are strings Ai = ai,1 ai,2 ... ai,p and Ai+1 = ai+1,1 ai+1,2 ... ai+1,q such that for some j <= min(p, q) ai,1 = ai+1,1, ai,2 = ai+1,2, ... ai,j = ai+1,j, then the second string is stored as [j]ai+1,j+1ai+1,j+2... ai+1,q, where [j] is a single character with code j.

If j = 0, that is, strings do not have any common prefix, then the second string is prefixed with zero byte, and so the total length actually increases.

Constraints

1 <= N <= 10000, 1 <= length(Ai) <= 255.


Input

First line of input contains integer number N, with following N lines containing strings A1 ... AN.


Output

Output must contain a single integer - minimal total length of compressed strings.


This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.


Sample Input

2

3
abc
atest
atext

2
test
notest


Sample Output

11

11


Source: Northeastern Europe 2003, Far-Eastern Subregion
Submit    Status