29510번 - Проект 다국어

문제

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

제한

힌트