Simple prefix compression

Time Limit: 2000MS

Memory Limit: 65536K

Description

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,1ai,2...ai,p and Ai + 1 = ai+1,1ai+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.

Sample Input

3
abc
atest
atext

Sample Output

11

Hint

Source

Northeastern Europe 2003, Far-Eastern Subregi

提交代码