Допоможи Васі
Вася готує черговий контест для весняних Всеберлянських зборів з програмування. Оскільки він любить веселі компанії, а погода сприяє, у нього залишилося зовсім мало часу на підготовку. Він хоче використати цей час максимально ефективно. Одним із завдань є швидке переміщення з однієї директорії в іншу. Вася настільки звик до свого улюбленого файлового менеджера "Near Commandir", що не може використовувати інший софт, адже це зайняло б у нього значно більше часу. Цей менеджер дозволяє виконувати кілька простих операцій: переміщення в списку файлів і піддиректорій на одну позицію вгору, переміщення вниз, вхід у піддиректорію, яка виділена в списку в даний момент. Якщо це батьківська директорія, ми піднімаємося на рівень вище в дереві каталогів. Кожна з цих операцій займає у Васі 1 секунду. Для прискорення Вася може також застосувати операцію зміни порядку файлів і піддиректорій у поточній директорії, яка займає t секунд. Файли в директорії можна сортувати за ім'ям, розміром і часом останньої зміни. У двох останніх випадках файли з однаковим розміром і часом сортуються за ім'ям. Імена файлів і каталогів у межах однієї директорії унікальні. Тепер він хоче дізнатися, скільки часу йому знадобиться, щоб перейти до потрібного файлу, якщо відомо, де він зараз знаходиться в дереві файлової системи. Спочатку файли в поточній директорії відсортовані за ім'ям, при вході в нову директорію файли також сортуються за ім'ям без додаткових часових витрат з боку Васі.
Вхідні дані
Файлова система задається деревом з виділеним коренем. У першому рядку містяться n і t (1 ≤ n ≤ 100000, 0 ≤ t ≤ 10) — розмір дерева і час зміни порядку файлів. Далі в наступних n рядках міститься по 4 числа p_i name_i fsize_i date_i (1 ≤ i ≤ n. p_i — номер вершини предка, якщо це -1, ця єдина вершина є коренем, name_i — ім'я файлу, непорожній рядок, що складається з не більше 10 латинських букв, fsize_i — розмір файлу, 0 ≤ fsize_i ≤ 10000. date_i — час останньої зміни файлу, 0 ≤ date_i ≤ 10000). В останньому рядку містяться два числа 0 ≤ s, f < n — номер вершини, на якій ми зараз стоїмо, і номер вершини, в яку потрібно потрапити. Вершини нумеруються в тому порядку, в якому вони подаються на вхід.
Вихідні дані
Виведіть одне ціле число - мінімальну кількість секунд.