e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

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

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

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

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

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

Входные данные

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

Выходные данные

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

Пример входных данныхПример выходных данных
prb5297

2

Time limit 2 seconds
Memory limit 64 MiB
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