Arcady is a copywriter. His today's task is to type up an already well-designed story using his favorite text editor.

Arcady types words, punctuation signs and spaces one after another. Each letter and each sign (including line feed) requires one keyboard click in order to be printed. Moreover, when Arcady has a non-empty prefix of some word on the screen, the editor proposes a possible autocompletion for this word, more precisely one of the already printed words such that its prefix matches the currently printed prefix if this word is unique. For example, if Arcady has already printed «codeforces», «coding» and «codeforces» once again, then there will be no autocompletion attempt for «cod», but if he proceeds with «code», the editor will propose «codeforces».

With a single click Arcady can follow the editor's proposal, i.e. to transform the current prefix to it. Note that no additional symbols are printed after the autocompletion (no spaces, line feeds, etc). What is the minimum number of keyboard clicks Arcady has to perform to print the entire text, if he is not allowed to move the cursor or erase the already printed symbols?

A word here is a contiguous sequence of latin letters bordered by spaces, punctuation signs and line/text beginnings/ends. Arcady uses only lowercase letters. For example, there are 20 words in «it's well-known that tic-tac-toe is a paper-and-pencil game for two players, x and o.».


-----Input-----

The only line contains Arcady's text, consisting only of lowercase latin letters, spaces, line feeds and the following punctuation signs: «.», «,», «?», «!», «'» and «-». The total amount of symbols doesn't exceed 3·10^5. It's guaranteed that all lines are non-empty.


-----Output-----

Print a single integer — the minimum number of clicks.


-----Examples-----
Input
snow affects sports such as skiing, snowboarding, and snowmachine travel.
snowboarding is a recreational activity and olympic and paralympic sport.

Output
141

Input
'co-co-co, codeforces?!'

Output
25

Input
thun-thun-thunder, thunder, thunder
thunder, thun-, thunder
thun-thun-thunder, thunder
thunder, feel the thunder
lightning then the thunder
thunder, feel the thunder
lightning then the thunder
thunder, thunder

Output
183



-----Note-----

In sample case one it's optimal to use autocompletion for the first instance of «snowboarding» after typing up «sn» and for the second instance of «snowboarding» after typing up «snowb». This will save 7 clicks.

In sample case two it doesn't matter whether to use autocompletion or not.

Difficulty: MEDIUM

Starter code:

Solutions:
class Trie:

	def __init__(self):
		self.letter___node = {}
		self.words_nr = 0

	def add_word(self, word):
		word = word + '$'
		curr_node = self
		for letter in word:
			if letter not in curr_node.letter___node:
				curr_node.letter___node[letter] = Trie()
			curr_node.words_nr += 1
			curr_node = curr_node.letter___node[letter]

	def check_word(self, word):
		word = word + '$'
		curr_node = self
		for letter in word:
			if letter not in curr_node.letter___node:
				return False
			curr_node = curr_node.letter___node[letter]
		return True

	def count_word(self, word):
		word = word + '$'
		curr_node = self
		curr_state = 0
		presses_saved = 0
		for letter in word:
			if letter not in curr_node.letter___node:
				if curr_state == 1:
					if '$' in curr_node.letter___node:
						return min(len(word) - 1, len(word) - 1 - presses_saved + 1)
					else:
						return len(word) - 1
				if curr_state == 0:
					return len(word) - 1
			if curr_node.words_nr > 1:
				curr_node = curr_node.letter___node[letter]
			elif curr_node.words_nr == 1:
				if curr_state == 0:
					curr_state = 1
				presses_saved += 1
				curr_node = curr_node.letter___node[letter]
			elif curr_node.words_nr == 0:
				if curr_state == 1:
					return min(len(word) - 1, len(word) - 1 - presses_saved + 1)
				elif curr_state == 0:
					return len(word) - 1
		if curr_node.words_nr == 0:
			presses_saved -= 1
			if curr_state == 1:
				return min(len(word) - 1, len(word) - 1 - presses_saved + 1)
			elif curr_state == 0:
				return len(word) - 1
text = ''
while 1:
	try:
		line = input()
		if line == '':
			raise Exception('e')
		text += line + '\n'
	except:
		break
ans = 0
syms = ['\n', '.', ',', '?', '!', "'", '-']
for sym in syms:
	text = text.replace(sym, ' ')
ans += text.count(' ')
idx___word = text.split(' ')
root = Trie()
root.add_word('$')
root.add_word('$$')
for word in idx___word:
	if word == '':
		continue
	count = root.count_word(word)
	check = root.check_word(word)
	ans += count
	if not check:
		root.add_word(word)
print(ans)


import sys

def read_text():
	text = ''
	for line in sys.stdin:
		text += line
	return text

def matching_word(word, bor, symbol, search):
	if symbol in search:
		search = search[symbol]
		word_found = 'size' in search and search['size'] == 1
		return (get_match(word, bor) if word_found else 0, search)
	return (0, ())

def contains_word(word, bor):
	search = bor
	for symbol in word:
		if symbol in search:
			search = search[symbol]
		else:
			return False
	words_left = 0
	for (key, value) in search.items():
		if key == 'size':
			continue
		words_left += value['size']
	return search['size'] - words_left == 1

def get_match(word, bor):
	search = bor
	match = ''
	for symbol in word:
		match += symbol
		search = search[symbol]
	while len(search.keys()) == 2:
		symbol = next(filter(lambda item: item != 'size', search.keys()))
		match += symbol
		search = search[symbol]
	return match

def add_to_bor(word, bor):
	search = bor
	for symbol in word:
		if symbol not in search:
			search[symbol] = dict([('size', 0)])
		search = search[symbol]
		search['size'] += 1

def replace_index(text, start, match):
	index = start
	for symbol in match:
		if symbol == text[index]:
			index += 1
		else:
			return -1
	return start + len(match) - 1

def get_updated_search(word, bor):
	search = bor
	for symbol in word:
		search = search[symbol]
	return search
text = list(read_text())
text_size = len(text)
bor = dict()
separators = ['.', ',', '?', '!', "'", '-', ' ', '\n']
typed = 0
index = 0
word = ''
search = bor
match = 0
while index < text_size:
	symbol = text[index]
	typed += 1
	if symbol not in separators:
		word += symbol
		if match != -1:
			(match, search) = matching_word(word, bor, symbol, search)
			if match != 0 and match != word:
				new_index = replace_index(text, index + 1 - len(word), match)
				if new_index != -1:
					typed += 1
					index = new_index
					word = match
					search = get_updated_search(word, bor)
				else:
					match = -1
	elif len(word) > 0:
		if not contains_word(word, bor):
			add_to_bor(word, bor)
		search = bor
		word = ''
		match = 0
	index += 1
print(typed)


class Ddict:

	def __init__(self):
		self.dicts = {}

	def add(self, key):
		d = self.dicts
		for i in key:
			if i not in d:
				d[i] = {}
			d = d[i]
		d[' '] = ''

	def find(self, key):
		if key == '':
			return ('', '')
		d = self.dicts
		q = []
		h = [key[0]]
		for i in key:
			if i not in d:
				if ' ' in d and len(d) == 1:
					return (''.join(q), ''.join(h))
				return ('', '')
			q.append(i)
			if len(d) != 1:
				h = q[:]
			d = d[i]
		if ' ' in d and len(d) == 1:
			return (''.join(q), ''.join(h))
		return ('', '')
words = Ddict()
ans = 0
while True:
	try:
		x = input()
		if not x:
			break
	except:
		break
	ans += len(x) + 1
	ws = [[]]
	for i in x:
		if i in ".,?!'- ":
			if ws[-1]:
				ws.append([])
		else:
			ws[-1].append(i)
	ws = list([''.join(e) for e in ws])
	for w in ws:
		(next_word, helped_word) = words.find(w)
		if next_word and next_word != helped_word:
			ans -= len(next_word) - len(helped_word) - 1
		words.add(w)
print(ans)


import sys
import re
SEPARATORS = "[.,? !'-]"

class TrieNode(object):

	def __init__(self):
		self.terminal = False
		self.go = {}
		self.count = 0

def insert(node, s):
	nodes = [node]
	(unique, auto) = (0, 0)
	for c in s:
		if c not in node.go:
			node.go[c] = TrieNode()
		node = node.go[c]
		nodes.append(node)
		if node.count == 1:
			unique += 1
		if node.terminal:
			auto = max(unique - 2, 0)
	if not node.terminal:
		node.terminal = True
		for node in nodes:
			node.count += 1
	return auto
root = TrieNode()
answer = 0
for line in sys.stdin:
	answer += len(line)
	for word in filter(None, re.split(SEPARATORS, line.strip())):
		answer -= insert(root, word)
print(answer)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class Trie:

	class Node:

		def __init__(self, char: int=1):
			self.char = char
			self.children = []
			self.counter = 1

	def __init__(self):
		self.root = Trie.Node()
		self.ans = 0

	def add(self, word):
		node = self.root
		for char in word:
			found_in_child = False
			for child in node.children:
				if child.char == char:
					child.counter += 1
					node = child
					found_in_child = True
					break
			if not found_in_child:
				new_node = Trie.Node(char)
				node.children.append(new_node)
				node = new_node

	def query(self, prefix, root=None):
		if not root:
			root = self.root
		node = root
		if not root.children:
			return 0
		prefix = [prefix]
		for char in prefix:
			char_not_found = True
			for child in node.children:
				if child.char == char:
					char_not_found = False
					node = child
					break
			if char_not_found:
				return 0
		return node
a = []
tr = Trie()
while True:
	try:
		s = input()
		if not s:
			break
	except EOFError:
		break
	a += [s]

def calc(s):
	node = tr.root
	found = False
	ind = -1
	its = 0
	for char in s:
		if not found:
			ind += 1
		next = tr.query(char, node)
		if not next:
			break
		if next.counter == 1 and (not found):
			found = True
		node = next
		its += 1
	if found and node.counter == 1:
		if not node.children:
			tr.ans += min(len(s), ind + 2 + len(s) - its)
		elif node.children:
			tr.ans += len(s)
		else:
			tr.ans += min(len(s), ind + 2)
	else:
		tr.ans += len(s)
	if not (its == len(s) and (not node.children)):
		tr.add(s)
for s in a:
	tr.ans += 1
	cur = []
	if 1:
		for k in s:
			if not k.isalpha():
				tr.ans += 1
				if cur:
					calc(cur)
					cur = []
			else:
				cur += [ord(k)]
		if cur:
			calc(cur)
print(tr.ans)