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