Problems
Помоги Васе
Помоги Васе
Вася подготавливает очередной контест для весенних Всеберляндских сборов по программированию. Так как он любитель весёлых компаний, да и сама погодан амекает, то на подготовку у него осталось совсем мало времени. Он хочет использовать его наиболее эффективно. Как одна из задач перед ним стоит не простая задача как можно быстрее попасть из одной директории в другую, причём он так привык к своему любимому файловому менеджеру "Near Commandir", что не может использовать другой софт, потому что это бы заняло у него гораздо больше времени. Этот менеджер умеет делать несколько простых операций: переместиться в списке файлов и поддиректорий на одну позицию вверх, переместиться вниз, войти в поддиректорию, которая выделена в списке в данный момент, причём если это родительская директория, мы поднимаемся на уровень выше в дереве каталогов. Каждая из этих простых операций занимает у Васи \textbf{1} секунду. Для ускорения Вася также может применить операцию изменения порядка файлов и поддиректорий в текущей директории, на эту операцию Вася затрачивает \textbf{t} секунд. Файлы в директории можно сортировать по имени, по размеру и времени последнего изменения. В двух последних случаях файлы с одинаковым размером и временем сортируются по имени. Имена файлов и каталогов в рамках одной директории уникальны. Теперь он хочет узнать, сколько времени ему потребуется, чтобы перейти на нужный ему файл, если известно, где он сейчас находится в дереве файловой системы. Изначально файлы в текущей директории отсортированы по имени, при входе в новую директорию файлы также сортируются по имени без дополнительных временных затрат со стороны Васи.
\InputFile
Файловая система задается деревом с выделенным корнем. В первой строке содержится \textbf{n} и \textbf{t} (\textbf{1} ≤ \textbf{n} ≤ \textbf{100000}, \textbf{0} ≤ \textbf{t} ≤ \textbf{10}) --- размер дерева и время изменения порядка файлов. Далее в следующих \textbf{n} строках содержится по \textbf{4} числа \textbf{p_i} \textbf{name_i} \textbf{fsize_i} \textbf{date_i} (\textbf{1} ≤ \textbf{i} ≤ \textbf{n}. \textbf{p_i} --- номер вершины предка, если это \textbf{-1}, эта единственная вершина является корнем, \textbf{name_i} --- имя файла, непустая строка, состоящая из не более \textbf{10} латинских букв, \textbf{fsize_i} --- размер файла, \textbf{0} ≤ \textbf{fsize_i} ≤ \textbf{10000}. \textbf{date_i} --- время последнего изменения файла, \textbf{0} ≤ \textbf{date_i} ≤ \textbf{10000}). В последней строке содержатся два числа \textbf{0} ≤ \textbf{s}, \textbf{f} < \textbf{n} --- номер вершины, на которой мы сейчас стоим, и номер вершины, в которую требуется попасть. Вершины нумеруются в том порядке, в котором они подаются на вход.
\OutputFile
Выведите одно целое число - минимальное количество секунд.
Input example #1
3 10 -1 usr 1 1 0 bin 1 1 1 python 1 1 2 0
Output example #1
4