eolymp
bolt
Try our new interface for solving problems
Problems

Восстановление HTML файла

Восстановление HTML файла

Time limit 2 seconds
Memory limit 64 MiB

Петя недавно скачал поврежденный HTML файл. Он выглядит как обычный HTML файл, но в нем есть некоторые несоответствия тэгов. Ваша задача - удалив минимальное количество открывающихся и закрывающихся тэгов сделать так, чтобы структура тэгов стала правильной.

Более формально, HTML файл состоит из произвольных символов с ASCII кодами из диапазона от 32 до 126, а также Linux-style переводов строки (символов с кодом 10). Тэги открываются следующим образом: <Имя тэга Параметры> и закрываются следующим образом <Имя тэга>. Имя тега - строка, состоящая из больших и маленьких латинских букв, которые считаются различными. Имя тэга отделяется от Параметров как минимум одним пробелом (но не переводом сроки). Параметры могут содержать произвольные допустимые ASCII символы кроме <, > и переводов строк. Также допускаются открывающиеся тэги без параметров и записываются в следующей форме: <Имя Тэга>.

HTML файл счиается правильным, если каждому открывающемуся тэгу можно привести в соответствие следующий далее в файле закрывающийся тэг таким образом, чтобы часть файла между этими тэгами также представляла собой правильный HTML файл, и аналогично можно привести в соответствие каждому закрывающемуся тэгу ровно один окрывающийся тэг идущий ранее в файле. HTML файл, не содержащий тэгов, также является правильным. Окрывающийся тэг считается соответствующим закрывающемуся, если у них одинаковое имя тэга.

Input data

Входной файл представляет из себя поврежденный HTML файл, который требуется исправить. Его длина не превосходит 10000 байт. Количество открывающихся и закрывающихся тэгов не превышает 500. Символы < и > не встречаются нигде, кроме окрывающихся и закрывающихся тэгов.

Output data

Выведите единственное целое число - минимальное количество окрывающихся/закрывающихся тэгов, которые требуется удалить, чтобы файл оказался правильным HTML файлом.

Examples

Input example #1
<a href=http://kruzhok.newmail.ru>
<b someone has corrupted this file>
It was a good file before...
</a>
</b>
Output example #1
2