꽃가루를 지켜라!

플라리아나 꽃과 호박벌은 열대우림에서 가장 좋은 협력 관계 중 하나를 이룬다. 봄이 되면 여러 꽃이 피고 꽃가루를 만들기 시작한다. 꽃들 사이에는 특별한 덩굴이 다리처럼 이어져 있어서, 한 꽃에서 다른 꽃으로 가는 길은 정확히 하나뿐이다.

각 꽃에는 벌 가족이 살고 있다. 이 가족은 그 꽃에 닿은 모든 덩굴을 지킨다. 그래서 덩굴 하나는 두 가족이 함께 지킨다. 꽃 $k$의 가족은 벌이 $s_k$마리이고 수분 능력은 $p_k$이다.

어느 날 벌 정찰병이 언덕 너머에 새로운 꽃밭이 생겼다고 알렸다. 그곳의 수분을 도울 벌 무리가 필요하다. 벌 여왕인 당신은 원정에 보낼 가족들을 고른다. 모든 덩굴에 대해, 그 덩굴을 지키는 두 가족 중 적어도 한 가족은 남아 있어야 덩굴이 계속 보호된다. 원정에 가는 가족의 벌은 모두 떠난다. 원정에 보낼 벌은 전체 $S$마리를 넘을 수 없다. 원정에 보낼 수 있는 수분 능력 합의 최댓값을 구하라.

첫 줄에 꽃의 개수 $N$ ($1 \leq N \leq 300$)과 보낼 수 있는 벌의 최대 수 $S$ ($1 \leq S \leq 300$)이 주어진다. 꽃은 1번부터 $N$번까지 번호가 매겨져 있다. 다음 $N$개의 줄에는 각 가족의 정보가 주어진다. 각 줄에는 가족의 벌 수 $s_k$ ($1 \leq s_k \leq 300$)와 수분 능력 $p_k$ ($1 \leq p_k \leq 100$)가 있다. 마지막 $N-1$개의 줄에는 덩굴 정보가 주어진다. 각 줄에는 서로 다른 두 정수 $u$ ($1 \leq u \leq N$)와 $v$ ($1 \leq v \leq N$)가 있으며, 꽃 $u$와 꽃 $v$ 사이에 덩굴이 있다는 뜻이다.

원정에 보낼 수 있는 수분 능력 합의 최댓값을 출력한다.