Loài hoa Flariana và loài ong nghệ tạo nên một mối quan hệ cộng sinh tuyệt vời trong rừng mưa nhiệt đới. Vào mùa xuân, nhiều loài hoa nở rộ và bắt đầu sản xuất phấn hoa. Những dây leo đặc biệt tạo nên một mạng lưới cầu nối giữa các bông hoa. Sử dụng dây leo, luôn tồn tại đúng một cách để đi từ một bông hoa đến bất kỳ bông hoa nào khác.

Mỗi bông hoa có một gia đình ong sống trên đó. Gia đình này bảo vệ tất cả các dây leo kết nối với bông hoa đó. Điều này có nghĩa là mỗi dây leo được bảo vệ bởi hai gia đình ong.

Gia đình ong ở bông hoa thứ \(k\) gồm \(s_k\) con ong và có sức thụ phấn là \(p_k\).

Một ngày nọ, một trinh sát ong thông báo rằng có một khu hoa mới phía bên kia đồi và họ cần một nhóm ong đến để giúp thụ phấn.

Là ong chúa, bạn phải chọn một tập các gia đình ong để cử đi làm nhiệm vụ. Với mỗi dây leo, phải có \textbf{ít nhất một trong hai gia đình hiện đang bảo vệ nó ở lại} để dây leo tiếp tục được bảo vệ. Tất cả ong trong các gia đình được chọn sẽ phải đi. Bạn chỉ có thể cử tối đa \(S\) con ong đi làm nhiệm vụ.

Hãy xác định tổng sức thụ phấn lớn nhất mà bạn có thể cử đi làm nhiệm vụ.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \leq N \leq 300)\) — số lượng bông hoa, và \(S\) \((1 \leq S \leq 300)\) — số lượng ong tối đa bạn có thể cử đi.
• Dòng tiếp theo gồm \(N\) dòng, mỗi dòng mô tả một gia đình ong với hai số nguyên \(s_k\) \((1 \leq s_k \leq 300)\) — số ong trong gia đình và \(p_k\) \((1 \leq p_k \leq 100)\) — sức thụ phấn của gia đình này.
• \(N - 1\) dòng cuối cùng mô tả các dây leo. Mỗi dòng gồm hai số nguyên \(u\) và \(v\) \((1 \leq u, v \leq N)\), biểu thị có một dây leo nối giữa bông hoa \(u\) và \(v\).

Dữ liệu ra

• In ra tổng sức thụ phấn lớn nhất mà bạn có thể cử đi làm nhiệm vụ.

Input 1

5 10
2 1
2 2
2 4
2 8
2 16
1 2
2 3
3 4
4 5

Output 1

21

Input 1

7 10
1 7
2 4
5 18
2 3
3 12
9 20
2 8
1 2
1 3
2 4
2 5
3 6
3 7

Output 1

33