D. Document Dimensions
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Hermione was really proud of her one million word text she wrote for her assignment. She was, until she realized that the text must be handed in on a single piece of paper with limited dimensions. Obviously, she could have just shortened her text, but Hermione decided to go another route. She decided to just copy her text to a new piece of paper, writing a little bit smaller... To make this easier, she decided to first change the line breaks in her text such that the sum of the height and width of the piece of paper is minimized. Given Hermione's text with $$$n$$$ words and assuming that each character takes up one unit height and one unit width, what is the minimal height plus width that can be achieved by inserting line breaks? Note that two words which are on the same line need to be separated by a single space.

Input

The input consists of:

  • One line with a single integer $$$n$$$ $$$(1\leq n\leq 10^6)$$$, the number of words.
  • One line with $$$n$$$ space separated words $$$w_i$$$ $$$(1\leq |w_i|\leq 10^6)$$$, consisting only of lowercase Latin letters.
It is guaranteed that the total length of the text, i.e. the sum of the lengths of the $$$n$$$ words, is not greater than $$$10^6$$$.
Output

Output a single integer, the sum of the height and width of the smallest piece of paper the text could fit on.

Examples
Input
4
i am lord voldemort
Output
11
Input
10
i solemnly swear that i am up to no good
Output
14