For Programming Excellence

A countless number of skills are required to be an excellent programmer. Different skills have different importance degrees, and the total programming competence is measured by the sum of products of levels and importance degrees of his/her skills.

In this summer season, you are planning to attend a summer programming school. The school offers courses for many of such skills. Attending a course for a skill, your level of the skill will be improved in proportion to the tuition paid, one level per one yen of tuition, however, each skill has its upper limit of the level and spending more money will never improve the skill level further. Skills are not independent: For taking a course for a skill, except for the most basic course, you have to have at least a certain level of its prerequisite skill.

You want to realize the highest possible programming competence measure within your limited budget for tuition fees.

Input

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

n k
h₁ ... h_n
s₁ ... s_n
p₂ ... p_n
l₂ ... l_n

• The first line has two integers, n, the number of different skills between 2 and 100, inclusive, and k, the budget amount available between 1 and 10⁵, inclusive. In what follows, skills are numbered 1 through n.
• The second line has n integers h₁...h_n, in which h_i is the maximum level of the skill i, between 1 and 10⁵, inclusive.
• The third line has n integers s₁...s_n, in which s_i is the importance degree of the skill i, between 1 and 10⁹, inclusive.
• The fourth line has n−1 integers p₂...p_n, in which p_i is the prerequisite skill of the skill i, between 1 and i−1, inclusive. The skill 1 has no prerequisites.
• The fifth line has n−1 integers l₂...l_n, in which l_i is the least level of prerequisite skill p_i required to learn the skill i, between 1 and h_pi , inclusive.

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

Output

For each dataset, output a single line containing one integer, which is 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, starting with level zero for all the skills. You do not have to use up all the budget.

Sample Input

3 10
5 4 3
1 2 3
1 2
5 2
5 40
10 10 10 10 8
1 2 3 4 5
1 1 2 3
10 10 10 10
5 10
2 2 2 5 2
2 2 2 5 2
1 1 2 2
2 1 2 1
0 0

Output for the Sample Input

18
108
35