Trò chơi đặt táo

Alice xây dựng một đồ thị có dạng là cây gồm \(n\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(n\), trong đó đỉnh \(1\) làm gốc. Đỉnh \(i\ (i > 1)\) sẽ có cạnh nối tới cha của nó là đỉnh \(p_i\ (1 \le p_i < i)\) với khoảng cách là \(w_i\). Số đỉnh nằm trên đường đi đơn từ nút gốc \(1\) đến một nút lá bất kỳ không vượt quá \(21\). Bob đề xuất một trò chơi trên cây như sau: Với hai số nguyên dương \(s\) và \(d\), Bob sẽ chọn \(s\) nút có số hiệu không vượt quá \(d\) để đặt \(s\) quả táo, Alice sẽ xuất phát tại đỉnh gốc \(1\) và tìm cách đi với tổng độ dài đường đi là ngắn nhất để thu thập được hết \(s\) quả táo rồi quay về đỉnh gốc.

Bob muốn làm khó Alice nên tìm cách đặt \(s\) quả táo để tổng độ dài đường đi của Alice là lớn nhất.

Yêu cầu: Cho cây mà Alice tạo và \(q\) lần chơi, mỗi lần chơi mô tả bằng hai số nguyên \(s\) và \(d\). Với mỗi lần chơi hãy đưa ra tổng độ dài đường đi của Alice trong trường hợp Bob biết cách đặt tối ưu.

Input

• Dòng đầu là hai số nguyên dương \(n, q\ (n \le 10^5)\).
• Dòng thứ hai chứa \(n - 1\) số nguyên dương \(p_2, p_3, \ldots, p_n\).
• Dòng thứ ba chứa \(n - 1\) số nguyên dương \(w_2, w_3, \ldots, w_n\ (w_i \le 10^9\) với \(2 \le i \le n)\).
• \(q\) dòng sau, mỗi dòng chứa hai số nguyên dương \(s, d\ (s, d \le n)\) mô tả một lần chơi.

Output

• Gồm \(q\) dòng, mỗi dòng là tổng độ dài đường đi của Alice trong trường hợp Bob biết cách đặt tối ưu cho lần chơi tương ứng.

Example

5 4
1 2 1 2
3 3 4 2
1 2
1 5
2 5
3 5

6
12
20
24

Scoring

• Có \(30\%\) số lượng test của bài có \(q = 1\) và \(n \le 100\).
• Có \(20\%\) số lượng test của bài có \(q = 1\).
• Có \(30\%\) số lượng test khác của bài có \(p_i = 1\) với \(2 \le i \le n\).
• Có \(20\%\) số lượng test còn lại không có ràng buộc nào thêm.