Khu nghỉ trượt tuyết có \(n\) điểm apres-ski tạo thành một cây gốc tại điểm \(1\). Mỗi dốc được hướng từ nhãn nhỏ hơn sang nhãn lớn hơn. Với mỗi \(i>1\), dốc \(i\) đi từ \(p_i\) đến \(i\), trong đó \(p_i<i\); dốc này có độ vui \(z_i\) và tốc độ \(b_i\). Mia chọn một lượt đi gồm nhiều nhất \(k\) dốc liên tiếp theo chiều các dốc. Gọi \(z_{first}\) và \(z_{last}\) là độ vui của dốc đầu và cuối; độ hỗn loạn của lượt đi là

trong đó tổng lấy trên các dốc của lượt đi. Khi \(k=1\), công thức vẫn giữ nguyên và hai dốc đầu, cuối trùng nhau. Hãy tìm độ hỗn loạn lớn nhất.

Dữ liệu vào

Dòng đầu chứa \(n,k\) (\(1\le k\le n\le3\cdot10^5\)). Dòng thứ hai chứa \(n-1\) số nguyên, số thứ \(i\) là \(p_{i+1}\) (\(1\le p_i<i\)). Dòng thứ ba chứa \(n-1\) số \(z_2,\ldots,z_n\) (\(1\le z_i\le10^5\)). Dòng thứ tư chứa \(n-1\) số \(b_2,\ldots,b_n\) (\(-10^5\le b_i\le10^5\)).

Dữ liệu ra

In độ hỗn loạn lớn nhất.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(14\) điểm: \(n\le1000\).
2. \(23\) điểm: với mọi \(1\le i<n\), có \(z_i=1\) và \(b_i>1\).
3. \(35\) điểm: \(n\le50000\).
4. \(38\) điểm: không có ràng buộc thêm.

Ví dụ

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

200

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

120

Nguồn

COCI 2025/2026 - Vòng 6, bài Skijanje.

Đề bài và dữ liệu kiểm thử được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.