프로젝트

타일 시공 팀이 어려운 시기를 맞았고, 관리 부서는 팀원들의 실력을 의심하고 있다. 팀은 자신들이 최고임을 증명하려 한다. 이를 위해 관리 부서가 생산성을 평가할 때 쓰는 지표를 인위적으로 끌어올리는 계획을 세웠다. 계획의 핵심은 $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$ ($2 \le i$)가 한 줄씩 주어진다. $a_i$는 $i$번째 방의 타일 시공이 끝나기 전에는 시작할 수 없는 방의 번호이다.

모든 방의 작업을 완료할 수 있는 계획이 존재함이 보장된다.

$k$개의 방 작업을 마치는 데 필요한 최소 시간을 출력한다.