33872번 - 원숭이도 나무에서 떨어진다

문제

밀림 속 배고픈 원숭이는 나무를 돌아다니며 바나나를 최대한 많이 수확하려고 한다. 밀림은 $N$개의 나무와 $N-1$개의 가지로 이루어져 있고, 각 나무는 1ドル$부터 $N$까지 번호가 매겨져 있다. 원숭이는 각 나무에서 가지를 이용하여 다른 모든 나무로 이동할 수 있다. 각 나무에는 일정량의 바나나가 열려 있으며, 원숭이는 해당 나무에 처음 방문했을 때만 바나나를 수확할 수 있다. 한 번 수확한 나무에서는 다시 바나나를 얻을 수 없다.

원숭이는 $S$번 나무를 먼저 방문한 후 $E$번 나무까지 이동하며 바나나를 수확하려 한다. 단, 어떤 나무에 천적인 매가 자리 잡고 있다면, 그 나무는 절대로 방문할 수 없으며 $S$와 $E$번 나무는 매가 존재하지 않는다. 또한, 원숭이는 체력을 $H$만큼 가지고 있으며, 나무를 한 번 이동할 때마다 체력이 1ドル$씩 감소한다.

원숭이는 같은 나무를 최대 2번까지만 방문할 수 있으며, 세 번째부터는 더 이상 해당 나무를 방문할 수 없다. 원숭이는 이동 중에 $E$번 나무를 경유할 수 있지만, 체력이 정확히 0ドル$이 되었을 때의 위치가 $E$번 나무여야만 바나나를 저장할 수 있다. 그렇지 않으면 아무리 바나나를 많이 수확했더라도 나무에서 떨어지면서 바나나를 모두 잃게 된다.

원숭이가 수확할 수 있는 바나나의 최대 개수를 구해보자.

입력

첫째 줄에 정수 $N$과 정수 $H$가 공백으로 구분되어 주어진다.$(2 \leq N \leq 25;1 \leq H \leq 25)$

둘째 줄에 시작 나무 번호 $S$와 도착 나무 번호 $E$가 공백으로 구분되어 주어진다. 시작 나무 번호와 도착 나무 번호는 항상 다르다.$(1 \leq S, E \leq N;S \neq E)$

셋째 줄에 $i$번 나무에 열려 있는 바나나 개수를 의미하는 $N$개의 정수 $B_1,\cdots,B_N$이 공백으로 구분되어 주어진다.$(0 \leq B_i \leq 10 ,000円)$

넷째 줄에 $i$번 나무에 매가 있는지 여부를 의미하는 $N$개의 정수 $K_1,\cdots,K_N$이 공백으로 구분되어 주어진다. 매가 있으면 1ドル,ドル 없으면 0ドル$이다.$(0 \leq K_i \leq 1)$

다섯째 줄부터 $N-1$개의 줄에 걸쳐 연결된 나무 쌍의 번호 $u, v$가 공백으로 구분되어 주어진다.$(1 \leq u, v \leq N)$

출력

체력이 0ドル$일 때 $E$번 나무에 도달할 수 있다면, 수확한 바나나의 최대 개수를 출력한다.

체력이 0ドル$일 때 $E$번 나무에 도달하지 못하면 -1을 출력한다.

제한

힌트