Vận động viên trượt tuyết Mia đã dành cả ngày ở một khu nghỉ dưỡng khá khác thường. Khu nghỉ dưỡng có ~n~ địa điểm après-ski (gọi tắt là apres) được nối với nhau bởi các đường trượt sao cho chúng tạo thành một cây liên thông gốc tại apres mang nhãn ~1~. Mỗi đường trượt đều có hướng từ apres có nhãn nhỏ hơn tới apres có nhãn lớn hơn.

Cây được mô tả như sau: với mỗi apres ~i > 1~, ta biết apres ~p_i~ mà từ đó có thể đi tới ~i~, tức là cha của ~i~ trong cây. Điều này xác định duy nhất toàn bộ các đường trượt; đường trượt số ~i~ dẫn tới apres ~i~.

Trong ngày, Mia đã trượt đúng một lần trên mỗi đường trượt và ghi nhớ với mỗi đường trượt:

• độ vui ~z_i~,
• vận tốc ~b_i~.

Đến cuối ngày, Mia muốn trượt thêm một lần nữa. Vì đã rất mệt, cô ấy sẽ chọn một cung trượt gồm nhiều nhất ~k~ đường trượt liên tiếp. Cung trượt phải đi đúng theo hướng của các đường trượt, tức từ apres có nhãn nhỏ hơn tới apres có nhãn lớn hơn. Sau khi trượt xong, Mia sẽ được trực thăng đón về nhà.

Với một cung trượt đã chọn, ta định nghĩa độ hỗn loạn của nó như sau. Gọi:

• ~z_{\text{first}}~ là độ vui của đường trượt đầu tiên trong cung,
• ~z_{\text{last}}~ là độ vui của đường trượt cuối cùng trong cung,
• ~b_i~ là vận tốc của các đường trượt trong cung đó.

Khi đó độ hỗn loạn của cung trượt là:

~z_{\text{last}} \cdot \left(z_{\text{last}} + \sum b_i\right) + z_{\text{first}}^2~.

Trong trường hợp cung chỉ có đúng ~1~ đường trượt thì công thức vẫn giữ nguyên, và khi đó ~z_{\text{first}} = z_{\text{last}}~.

Hãy xác định độ hỗn loạn lớn nhất của một cung trượt mà Mia có thể chọn.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~.

Dòng thứ hai chứa ~n-1~ số nguyên; số thứ ~i~ cho biết từ apres nào có thể đi tới apres mang nhãn ~i+1~, tức là ~p_i~.

Dòng thứ ba chứa ~n-1~ số nguyên; số thứ ~i~ là độ vui ~z_i~ của đường trượt số ~i+1~.

Dòng thứ tư chứa ~n-1~ số nguyên; số thứ ~i~ là vận tốc ~b_i~ của đường trượt số ~i+1~.

Output

In ra trên một dòng duy nhất độ hỗn loạn lớn nhất của một cung trượt hợp lệ.

Ràng buộc

• ~1 \le k \le n \le 3 \cdot 10^5~
• ~1 \le p_i \le i~
• ~1 \le z_i \le 10^5~
• ~-10^5 \le b_i \le 10^5~

Chấm điểm

• Subtask 1 (14 điểm): ~n \le 1000~
• Subtask 2 (23 điểm): Với mọi ~1 \le i < n~, ta có ~z_i = 1~ và ~b_i > 1~
• Subtask 3 (35 điểm): ~n \le 50000~
• Subtask 4 (38 điểm): Không có ràng buộc bổ sung.

Sample Input 1

5 1
1 2 2 1
5 4 8 7
6 3 9 3

Sample Output 1

200

Sample Input 2

9 2
1 2 1 1 4 3 6 5
1 3 7 8 4 1 8 2
1 -7 -1 -6 3 8 -1 6

Sample Output 2

120

Giải thích

• Ví dụ 1: Vì ~k = 1~, cung trượt chỉ có thể gồm đúng ~1~ đường trượt. Khi đó độ hỗn loạn của bốn đường trượt lần lượt là ~80~, ~44~, ~200~, ~119~, nên đáp án là ~200~.