Tý có \(N\) cuốn sách cần xếp lên kệ theo thứ tự. Cuốn \(i\) dày \(w_i\), cao \(h_i\). Mỗi tầng chứa một số cuốn liên tiếp với tổng độ dày không quá \(W\). Chiều cao tầng bằng chiều cao lớn nhất của các cuốn trong tầng. Tổng chiều cao kệ là tổng chiều cao các tầng.

Hãy xếp sao cho tổng chiều cao nhỏ nhất.

Đị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

Dữ liệu vào

• Dòng đầu gồm \(N, W\) (\(1 \le N \le 10^5\), \(1 \le W \le 10^9\)).
• \(N\) dòng sau, mỗi dòng \(h_i, w_i\) (\(1 \le h_i \le 10^6\), \(1 \le w_i \le W\)).

Kết quả ra

• In ra tổng chiều cao nhỏ nhất.

Ví dụ

Input

5 10
5 7
3 2
4 3
6 5
2 1

Output

12

Subtask