優秀なプログラマになるには

優秀なプログラマになるためには，数えきれないほどの種類のスキルが必要である． スキルの種類によって重要性は異なっており， プログラミングの総合力は各スキルのレベルと重要性の積の総和で評価される．

あなたはこの夏，夏期プログラミング講習の受講を考えている． 講習には種々のスキルのためのコースがある． あるスキルのためのコースを受講すれば， そのスキルのレベルが払った授業料に比例して， 1 円払うごとに 1 レベルだけ高まるが， スキルのレベルにはそれぞれ上限があり，いくらお金をかけてもそれ以上に高めることはできない． また，各スキルは独立ではなく，最も基礎的なコース以外は， 各コースの受講のためには，その前提となるスキルがあるレベル以上でなければならない．

あなたは限られた予算内でプログラミング総合力評価をできるだけ高めたい．

Input

入力は最大 100 個のデータセットからなる． 各データセットは次の形式で表される．

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

• 1 行目の 2 つの整数は， n がスキルの種類数を表し 2 以上 100 以下， k が使える予算額を表し 1 以上 10⁵ 以下である． 以下では各スキルは 1 から n までの番号で表す．
• 2 行目の n 個の整数 h₁...h_n の各 h_i はスキル i のレベルの上限であり， 1 以上 10⁵ 以下である．
• 3 行目の n 個の整数 s₁...s_n の各 s_i はスキル i の重要度であり， 1 以上 10⁹ 以下である．
• 4 行目の n−1 個の整数 p₂...p_n の各 p_i はスキル i の前提となるスキルの番号であり， 1 以上 i 未満である． スキル 1 の前提となるスキルはない．
• 5 行目の n−1 個の整数 l₂...l_n の各 l_i はスキル i の習得に最低限必要である前提スキル p_i のレベルであり， 1 以上 h_pi 以下である．

入力の終わりは，2 つのゼロからなる行で表される．

Output

各データセットについて， 全スキルのレベルがゼロの状態から始めて， 授業料予算の範囲内で到達できる最高のプログラミング総合力評価値， すなわち各スキルのレベルと重要性の積の総和の最大値を， ひとつの整数として1行に出力せよ． 予算は使い切らなくてもかまわない．

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

---