Проект

У артели по укладке квадратных плиток наступили тяжелые времена. Начальство сомневается в квалификации работников. Естественно, работники артели хотят доказать, что они --- лучшие из лучших. Для этого они разработали проект по искусственному повышению характеристик, используемых начальством для оценки продуктивности работ. Ключевым моментом в нем является выполнение отделки $k$ комнат в кратчайшие сроки.

На данный момент к ним поступили заказы на выполнение работ в $n$ комнатах. Про каждую комнату известно, какое минимальное количество дней потребуется для выполнения работ в ней. Артель не может работать более чем над одной комнатой в течение дня. Кроме того, есть еще одна трудность --- известно, что для каждой комнаты, кроме первой, укладку плитки в этой комнате обязательно нужно завершить прежде, чем начинать работы в какой-то другой комнате. Это правило было введено для согласования работ с другими артелями.

Помогите работникам артели по укладыванию квадратных плиток определить, какое минимальное количество времени уйдет на выполнение работ в $k$ комнатах.

Первая строка входного файла содержит два целых числа $n$ и $k$, разделенных пробелом ($1 \le n \le 5 \cdot 10^4$, $1 \le k \le 40$, $k \le n$). В следующей строке $n$ целых чисел $t_i$ ($1 \le t_i \le 10^7$) --- времена выполнения работ в комнатах. Каждая из следующих $n - 1$ строк содержит целое число $a_i$ --- номер комнаты, работы в которой нельзя начинать до окончания укладки плитки в $i$-й комнате ($2 \le i$). Гарантируется, что существует план выполнения работ, позволяющий выполнить работы во всех комнатах.

Выведите минимальное время, необходимое для выполнения работ в $k$ комнатах.