Ромин папа работает в стремительно развивающейся корпорации «РосКошки». Сегодня папа решил показать своему сыну свою компанию, ведь он планирует, что со временем все его дети и внуки будут работать в «РосКошках». Рома — мальчик любознательный, поэтому он довольно быстро узнал всё о структуре корпорации.

Всего в «РосКошках» работает N сотрудников, у каждого из которых (кроме президента) есть один непосредственный начальник. Чтобы сотрудники не отвлекались по мелочам, президент запретил им во время работы общаться с кем-либо, кроме своих непосредственных подчинённых и начальника. Поэтому все сообщения сотрудникам приходится передавать через других сотрудников. Пока Рома без дела бродил по коридорам фирмы, он не только узнал для каждого сотрудника, сколько ему требуется минут, чтобы передать сообщение одному из своих подчинённых или начальнику, но и обнаружил, что в этой фирме работает сисадмин, который имеет особый статус: у него нет ни начальников, ни подчинённых, и он может передавать сообщения любому сотруднику фирмы, причём мгновенно. Но при этом, если у сотрудника есть хотя бы один подчинённый, он никогда не подойдёт к сисадмину с просьбой передать сообщение кому-либо. Рома осознал, что только что ему открылся новый способ передачи информации внутри корпорации, поэтому разузнал для каждого сотрудника, не имеющего подчинённых, сколько ему требуется времени, чтобы дойти до сисадмина.

Ромин папа хорошо осознаёт масштабы любопытства своего сына, поэтому, когда ему в очередной раз потребовалось передать своему другу срочное сообщение, он обратился к своему сыну. Помогите Роме минимизировать время, необходимое для передачи папиного сообщения его другу.

Каждый раз, когда в мире происходит значимое событие, наша реальность разветвляется на несколько — в зависимости от исхода этого события. После этого существует уже не только наша основная реальность, но и ответвившиеся от неё в моменты появления разных исходов.

Однажды один архимаг решил сделать мир лучше. Такая грандиозная задача не под силу одному архимагу, поэтому он решил найти самого себя ещё в K реальностях и выполнить эту задачу вместе. Проведённое теоретическое исследование показало, что, кроме реальности, в которой находится именно он, существует ещё N - 1 реальностей. Для удобства они были занумерованы числами от 1 до N, при этом его собственная реальность имеет номер 1, а посетить ему необходимо реальности с номерами 2, 3, ..., K + 1.

Как уже говорилось, каждая реальность когда-то ответвилась от некоторой другой, за исключением одной Начальной реальности, которая существовала всегда (её номер может оказаться каким угодно; считается, что она появилась в момент времени 0). Исследование показало, что реальность с номером i ответвилась от реальности с номером P_i в момент времени T_i. Из каждой реальности с номером i архимаг может переместиться

• в любую ответвившуюся от неё, то есть в любую j, такую что P_j = i;
• в P_i, если i — не Начальная реальность.

Требуется найти минимальное количество энергии, которое потребуется архимагу, чтобы, начав в реальности с номером 1, посетить все реальности с номерами от 2 до K + 1 (в любом порядке) и затем вновь вернуться в 1. Любую реальность при этом разрешается посещать сколько угодно раз.