프로그래밍 역량의 극대화

뛰어난 프로그래머가 되려면 셀 수 없이 많은 기술이 필요하다. 기술마다 중요도가 다르며, 프로그래밍 역량은 각 기술의 수준과 중요도를 곱한 값들의 합으로 측정한다.

이번 여름에 여름 프로그래밍 학교에 다닐 계획이다. 학교에는 이런 기술 여러 가지에 대한 강좌가 있다. 어떤 기술의 강좌를 들으면, 낸 수업료에 비례해 그 기술의 수준이 오른다. 수업료 1엔마다 수준이 1씩 오른다. 다만 기술마다 수준의 상한이 있어서, 그 이상 돈을 써도 수준은 더 오르지 않는다. 기술은 서로 독립적이지 않다. 가장 기초적인 강좌를 제외하면, 어떤 기술의 강좌를 들으려면 선수 기술이 일정 수준 이상이어야 한다.

주어진 수업료 예산 안에서 프로그래밍 역량을 가능한 한 가장 높게 만들고자 한다.

입력은 최대 100개의 데이터셋으로 이루어지며, 각 데이터셋은 다음 형식으로 주어진다.

n k
h1 ... hn
s1 ... sn
p2 ... pn
l2 ... ln

첫째 줄에는 기술의 개수 $n$ ($2 \le n \le 100$)과 예산 $k$ ($1 \le k \le 10^5$)가 정수로 주어진다. 기술은 1번부터 $n$번까지 번호가 매겨진다.

둘째 줄에는 $n$개의 정수 $h_1 \dots h_n$이 주어진다. $h_i$는 기술 $i$의 최대 수준이며, 1 이상 $10^5$ 이하이다.

셋째 줄에는 $n$개의 정수 $s_1 \dots s_n$이 주어진다. $s_i$는 기술 $i$의 중요도이며, 1 이상 $10^9$ 이하이다.

넷째 줄에는 $n-1$개의 정수 $p_2 \dots p_n$이 주어진다. $p_i$는 기술 $i$의 선수 기술이며, 1 이상 $i-1$ 이하이다. 기술 1에는 선수 기술이 없다.

다섯째 줄에는 $n-1$개의 정수 $l_2 \dots l_n$이 주어진다. $l_i$는 기술 $i$를 배우기 위해 필요한 선수 기술 $p_i$의 최소 수준이며, 1 이상 $h_{p_i}$ 이하이다.

입력의 끝은 0 0이 한 줄에 적힌 것으로 나타낸다.

각 데이터셋에 대해, 주어진 수업료 예산 안에서 달성할 수 있는 프로그래밍 역량의 최댓값을 한 줄에 정수 하나로 출력한다. 역량은 각 기술의 수준과 중요도를 곱한 값들의 합이다. 모든 기술의 수준은 0에서 시작한다. 예산을 전부 쓸 필요는 없다.