For Programming Excellence

時間制限 : 8 sec, メモリ制限 : 262144 KB
英語版はこちら

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

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

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

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

Input

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

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

  • 1 行目の 2 つの整数は, n がスキルの種類数を表し 2 以上 100 以下, k が使える予算額を表し 1 以上 105 以下である. 以下では各スキルは 1 から n までの番号で表す.
  • 2 行目の n 個の整数 h1...hn の各 hi はスキル i のレベルの上限であり, 1 以上 105 以下である.
  • 3 行目の n 個の整数 s1...sn の各 si はスキル i の重要度であり, 1 以上 109 以下である.
  • 4 行目の n−1 個の整数 p2...pn の各 pi はスキル i の前提となるスキルの番号であり, 1 以上 i 未満である. スキル 1 の前提となるスキルはない.
  • 5 行目の n−1 個の整数 l2...ln の各 li はスキル i の習得に最低限必要である前提スキル pi のレベルであり, 1 以上 hpi 以下である.

入力の終わりは,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

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Yokohama, Japan, 2018-07-6
https://icpc.iisf.or.jp/2018-yokohama/