Допоможи Васі#3704

Допоможи Васі

1 секунда

256 мегабайтів

Дуже складна

Вася готує черговий контест для весняних Всеберлянських зборів з програмування. Оскільки він любить веселі компанії, а погода сприяє, у нього залишилося зовсім мало часу на підготовку. Він хоче використати цей час максимально ефективно. Одним із завдань є швидке переміщення з однієї директорії в іншу. Вася настільки звик до свого улюбленого файлового менеджера "Near Commandir", що не може використовувати інший софт, адже це зайняло б у нього значно більше часу. Цей менеджер дозволяє виконувати кілька простих операцій: переміщення в списку файлів і піддиректорій на одну позицію вгору, переміщення вниз, вхід у піддиректорію, яка виділена в списку в даний момент. Якщо це батьківська директорія, ми піднімаємося на рівень вище в дереві каталогів. Кожна з цих операцій займає у Васі $1$ секунду. Для прискорення Вася може також застосувати операцію зміни порядку файлів і піддиректорій у поточній директорії, яка займає $t$ секунд. Файли в директорії можна сортувати за ім'ям, розміром і часом останньої зміни. У двох останніх випадках файли з однаковим розміром і часом сортуються за ім'ям. Імена файлів і каталогів у межах однієї директорії унікальні. Тепер він хоче дізнатися, скільки часу йому знадобиться, щоб перейти до потрібного файлу, якщо відомо, де він зараз знаходиться в дереві файлової системи. Спочатку файли в поточній директорії відсортовані за ім'ям, при вході в нову директорію файли також сортуються за ім'ям без додаткових часових витрат з боку Васі.

Вхідні дані

Файлова система задається деревом з виділеним коренем. У першому рядку містяться $n$ і $t$ ( $1 \leq n \leq 100000$ 1 \leq n \leq 100000, $0 \leq t \leq 10$ 0 \leq t \leq 10) — розмір дерева і час зміни порядку файлів. Далі в наступних $n$ рядках міститься по $4$ значення $p_{i}$ p_i $nam e_{i}$ name_i $f s i z e_{i}$ fsize_i $d a t e_{i}$ date_i ( $1 \leq i \leq n$ 1 \leq i \leq n. $p_{i}$ p_i — номер вершини предка, якщо це $- 1$ , ця єдина вершина є коренем, $nam e_{i}$ name_i — ім'я файлу, непорожній рядок, що складається з не більше $10$ латинських букв, $f s i z e_{i}$ fsize_i — розмір файлу, $0 \leq f s i z e_{i} \leq 10000$ 0 \leq fsize_i \leq 10000. $d a t e_{i}$ date_i — час останньої зміни файлу, $0 \leq d a t e_{i} \leq 10000$ 0 \leq date_i \leq 10000). В останньому рядку містяться два числа $0 \leq s$ 0 \leq s, $f < n$ f < n — номер вершини, на якій ми зараз стоїмо, і номер вершини, в яку потрібно потрапити. Вершини нумеруються в тому порядку, в якому вони подаються на вхід.

Вихідні дані

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

Приклади

Приклад 1