eolymp
bolt
Try our new interface for solving problems
Məsələlər

Помоги Васе

Помоги Васе

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Вася подготавливает очередной контест для весенних Всеберляндских сборов по программированию. Так как он любитель весёлых компаний, да и сама погодан амекает, то на подготовку у него осталось совсем мало времени. Он хочет использовать его наиболее эффективно. Как одна из задач перед ним стоит не простая задача как можно быстрее попасть из одной директории в другую, причём он так привык к своему любимому файловому менеджеру "Near Commandir", что не может использовать другой софт, потому что это бы заняло у него гораздо больше времени. Этот менеджер умеет делать несколько простых операций: переместиться в списке файлов и поддиректорий на одну позицию вверх, переместиться вниз, войти в поддиректорию, которая выделена в списке в данный момент, причём если это родительская директория, мы поднимаемся на уровень выше в дереве каталогов. Каждая из этих простых операций занимает у Васи 1 секунду. Для ускорения Вася также может применить операцию изменения порядка файлов и поддиректорий в текущей директории, на эту операцию Вася затрачивает t секунд. Файлы в директории можно сортировать по имени, по размеру и времени последнего изменения. В двух последних случаях файлы с одинаковым размером и временем сортируются по имени. Имена файлов и каталогов в рамках одной директории уникальны. Теперь он хочет узнать, сколько времени ему потребуется, чтобы перейти на нужный ему файл, если известно, где он сейчас находится в дереве файловой системы. Изначально файлы в текущей директории отсортированы по имени, при входе в новую директорию файлы также сортируются по имени без дополнительных временных затрат со стороны Васи.

Giriş verilənləri

Файловая система задается деревом с выделенным корнем. В первой строке содержится n и t (1n100000, 0t10) — размер дерева и время изменения порядка файлов. Далее в следующих n строках содержится по 4 числа p_iname_ifsize_idate_i (1in. p_i — номер вершины предка, если это -1, эта единственная вершина является корнем, name_i — имя файла, непустая строка, состоящая из не более 10 латинских букв, fsize_i — размер файла, 0fsize_i10000. date_i — время последнего изменения файла, 0date_i10000). В последней строке содержатся два числа 0s, f < n — номер вершины, на которой мы сейчас стоим, и номер вершины, в которую требуется попасть. Вершины нумеруются в том порядке, в котором они подаются на вход.

Çıxış verilənləri

Выведите одно целое число - минимальное количество секунд.

Nümunə

Giriş verilənləri #1
3 10
-1 usr 1 1
0 bin 1 1
1 python 1 1
2 0
Çıxış verilənləri #1
4
Mənbə III International Summer School Programming in Sevastopol 2012