For Programming Excellence

A programmer needs countless skills to become excellent. Each skill has its own importance degree, and the total programming competence is the sum of the products of each skill's level and its importance degree.

This summer, you plan to attend a summer programming school. The school offers courses for many of these skills. When you take a course for a skill, its level rises in proportion to the tuition you pay, one level per one yen. Each skill has an upper limit on its level, and spending more on it does not raise the level past that limit. Skills depend on one another. Except for the most basic course, a course for a skill requires that its prerequisite skill be at least a certain level.

You want the highest possible programming competence within your tuition budget.

The input consists of no more than 100 datasets, each in the following format.

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

The first line has two integers, $n$, the number of skills ($2 \le n \le 100$), and $k$, the tuition budget ($1 \le k \le 10^5$). Skills are numbered 1 through $n$.

The second line has $n$ integers $h_1 \dots h_n$. $h_i$ is the maximum level of skill $i$, between 1 and $10^5$ inclusive.

The third line has $n$ integers $s_1 \dots s_n$. $s_i$ is the importance degree of skill $i$, between 1 and $10^9$ inclusive.

The fourth line has $n-1$ integers $p_2 \dots p_n$. $p_i$ is the prerequisite skill of skill $i$, between 1 and $i-1$ inclusive. Skill 1 has no prerequisite.

The fifth line has $n-1$ integers $l_2 \dots l_n$. $l_i$ is the least level of prerequisite skill $p_i$ required to learn skill $i$, between 1 and $h_{p_i}$ inclusive.

The end of the input is a line containing two zeros.

For each dataset, output one line containing a single integer: the highest programming competence measure achievable, that is, the maximum sum of the products of levels and importance degrees of the skills, within the given tuition budget. All skills start at level zero. You do not have to use up the whole budget.