꽃가루를 지켜라!

Flariana 꽃들과 뒤영벌들은 열대 우림에서 가장 멋진 공생 관계 중 하나를 이룬다. 봄이 되면 여러 꽃이 피어 꽃가루를 생산하기 시작한다. 특별한 덩굴들이 꽃 사이를 잇는 다리의 연결망을 이룬다. 덩굴을 이용하면 각 꽃에서 다른 어떤 꽃으로든 가는 방법이 정확히 하나 있다.

모든 꽃에는 벌 한 가족이 산다. 이 가족은 그 꽃에 닿아 있는 모든 덩굴을 보호한다. 따라서 모든 덩굴은 두 가족의 보호를 받는다. 꽃 $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$ 사이에 덩굴이 있음을 나타낸다.

임무에 보낼 수 있는 수분 능력의 총합의 최댓값을 출력한다.