시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB21150.000%

문제

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

예제 입력 1

5 2
1 2 3 4 5
1
1
2
2

예제 출력 1

7

예제 입력 2

5 3
1 2 3 4 5
1
1
2
2

예제 출력 2

11