모든 결말을 보고 싶어

긴 여행을 마치고 집으로 돌아온 현욱은 2주 뒤에 소프트콘 대회가 열린다는 이야기를 듣고 참가하기로 했다. 그러나 여행으로 많이 지쳐서, 대회 준비에 앞서 최근에 산 게임을 먼저 플레이하기로 했다.

이 게임은 스토리가 진행되는 도중에 선택지가 나타나고, 플레이어의 선택에 따라 이야기가 여러 갈래로 나뉘는 구조이다.

게임은 총 $N$개의 장면으로 이루어져 있고, 각 장면에는 $N$ 이하의 자연수 번호가 붙어 있다. 번호는 중복되지 않는다. 게임은 1번 장면에서 시작하며, 시작 장면에서 어떤 장면에 도달하는 방법은 하나뿐이다. 또한 이미 본 장면을 다시 보는 일은 없다. 각 장면이 끝날 때마다 저장할 기회가 주어진다. 그 뒤 최대 2개의 선택지가 주어지고, 고른 선택지에 따라 서로 다른 장면으로 넘어간다.

저장하면 언제든지 불러와서 다시 선택할 수 있다. 저장 횟수에는 제한이 없다. 다만 $i$번째 장면에서 저장하려면 $M_i$만큼의 돈을 내야 한다. 저장 비용은 장면을 지날 때마다 줄어든다. 즉, 장면 $A$에서 장면 $B$로 넘어갈 수 있다면 $B$에서 저장하는 비용은 $A$에서 저장하는 비용보다 작거나 같다. 현욱은 용돈이 부족해서, 저장에 쓰는 돈을 합쳐 $K$ 이하로 맞추려고 한다.

선택지가 없는 장면이 끝나면 결말이 나온다. 모든 결말은 서로 다르다.

현욱은 모든 결말을 보고 싶다. 결말을 볼 때가 가장 기분 좋기 때문에, 대회가 끝난 뒤에 모든 결말을 몰아서 보려고 한다. 그때 모든 결말을 가능한 한 짧은 시간에 보고 싶다. 그래서 지금 게임 중간중간에 미리 저장해 두고, 대회가 끝난 뒤에는 저장한 지점부터 이어서 플레이하려고 한다. 프롤로그 영상이 너무 길기 때문에, 대회가 끝난 뒤에는 항상 이전에 저장했던 곳부터 시작한다.

현욱은 이미 인터넷에서 공략집을 찾아서 장면들이 어떻게 연결되어 있는지 모두 알고 있다. 대회가 끝난 뒤 모든 결말을 보는 데 걸리는 시간을 최소화하라. 한 장면을 플레이하는 데 1분이 걸리고, 그 밖의 시간은 걸리지 않는다고 가정한다.

첫 줄에 장면의 개수 $N$과 쓸 수 있는 돈 $K$가 공백으로 구분되어 주어진다. 두 수는 모두 0보다 큰 정수이다.

둘째 줄에 각 장면에서 저장하는 데 필요한 비용 $M_i$가 주어진다. $1 \le M_i \le K$이고, $M_i$는 모두 정수이다.

다음 $N-1$개의 줄에 두 자연수 $A$, $B$($1 \le A, B \le N$)가 공백으로 구분되어 주어진다. 이는 $A$ 장면에서 $B$ 장면으로 넘어가는 선택을 할 수 있다는 뜻이다. 이때 $B$에서 저장하는 비용 $X$는 항상 $A$에서 저장하는 비용 $Y$보다 작거나 같다.

첫 줄에 대회가 끝난 후 모든 결말을 보기 위해 플레이해야 하는 최소 시간을 분 단위로 출력한다.

• $1 \le N \le 10000$
• $1 \le K \le 5000$