Bé Tý đang chuẩn bị đồ cho chuyến cắm trại. Đồ đạc của Tý được sắp xếp theo cấu trúc cây: mỗi món đồ có một trọng lượng \(w_i\) và giá trị sử dụng \(v_i\). Để mang một món đồ, Tý bắt buộc phải mang tất cả đồ trên đường từ gốc (món số \(1\)) đến món đồ đó. Nói cách khác, tập đồ được chọn phải là một cây con chứa gốc \(1\).

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

Ba lô của Tý chỉ chịu được tổng trọng lượng tối đa \(W\). Hãy giúp Tý chọn đồ để tổng giá trị sử dụng là lớn nhất.

Đầu vào:

• Dòng đầu gồm \(N\) và \(W\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) gồm \(w_i, v_i\) (\(1 \le w_i \le W, 1 \le v_i \le 10^9\)).
• \(N - 1\) dòng cuối, mỗi dòng gồm \(u, v\).

Đầu ra:

• Một số nguyên là tổng giá trị lớn nhất đạt được.