ACM 2003 - Simple prefix compression

Problem F. Simple prefix compression ≡

problems
details
visible spaces
basic formulae
wide text
editor

Author:	A. Klenin	Time limit:	2 sec
Input file:	input.txt	Memory limit:	200 Mb
Output file:	output.txt

Statement

Many databases store the data in the character fields (and especially indices) using prefix compression. This technique compresses a sequence of strings A₁, ..., A_N by the following method: if there are strings A_i = a_i,1a_i,2...a_i,p and A_{i + 1} = a_i+1,1a_i+1,2...a_i+1,q

such that for some j ≤ min(p, q) a_i,1 = a_i+1,1, a_i,2 = a_i+1,2, ... a_i,j = a_i+1,j, then the second string is stored as [j]a_i+1,j+1a_i+1,j+2... a_i+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.

Input file format

First line of input file contains integer number N, with following N lines containing strings A₁ ... A_N

Output file format

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

Constraints

1 ≤ N ≤ 10000, 1 ≤ length(A_i) ≤ 255.

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`3 abc atest atext`	`11`
2	`2 test notest`	`11`