15985번 - 모든 결말을 보고 싶어 서브태스크

긴 여행을 마치고 집으로 돌아온 현욱은 2주일 뒤 소프트콘 대회가 열린다는 이야기를 듣고 참가를 결심했다. 하지만 바로 대회를 준비하기엔 여행이 너무 피곤했기 때문에, 현욱은 최근에 구매한 게임을 일단 좀 플레이하기로 했다.

 이 게임은 스토리가 진행되는 도중 선택지가 나타나며, 플레이어의 선택에 의해 이야기의 갈래가 나누어지는 구조로 되어 있다.

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

저장을 하면 언제든지 불러온 후 다시 선택을 할 수 있다. 저장의 횟수에는 제한이 없으나, i번째 장면에서 저장을 하려면 M_i만큼의 돈을 지불해야 한다. 또, 저장하는데 필요한 비용은 장면을 지날 때마다 줄어든다. 즉, 어떤 장면 A에서 장면 B로 넘어갈 수 있다면 B에서 저장하는 비용은 항상 A에서 저장하는 비용보다 작거나 같다. 현욱은 용돈이 부족하기 때문에 저장하는 데에 돈을 K 이하로 사용하려고 한다. 선택지가 없는 장면이 끝나면 결말이 나오며, 모든 결말은 서로 다르다.

현욱은 모든 결말을 보고 싶다. 결말을 볼 때가 가장 기분이 좋기 때문에, 현욱은 모든 결말을 소프트콘 대회가 끝난 뒤에 몰아서 보려고 하고, 그 때 모든 결말을 가능한 짧은 시간 내에 다 보려고 한다. 오늘은 그 때를 위해 사전 작업을 하기로 했다. 즉, 미리 게임의 중간 중간에 저장을 해두고, 대회가 끝난 뒤에 그 지점들부터 이어서 플레이하려고 한다. 또한 게임을 새로 시작할 때 나오는 프롤로그 영상이 너무 길기 때문에, 대회가 끝난 뒤에 플레이할 때는 항상 이전에 저장했던 곳부터 시작하려고 한다.

현욱은 이미 인터넷에서 공략집을 찾아, 장면들이 연결된 상태를 모두 알고 있다. 현욱이 소프트콘 대회가 끝난 후에 모든 결말을 보는 데에 걸리는 시간을 최소화하여라. 한 장면을 플레이하는 데에는 1분이 소요되며, 그 외에는 시간이 소요되지 않는다고 가정한다.

첫 줄에 장면의 개수 N과 쓸 수 있는 돈 K 가 공백을 사이에 두고 주어진다.  두 수는 모두 0보다 큰 정수이다.
둘째 줄에 각 노드에 저장하기 위해 필요한 비용 M_i (1 ≤ M_i ≤ K) 가 주어진다. M_i는 모두 정수이다.
다음 줄부터 N-1개의 줄에 걸쳐 두 자연수 A, B (1 ≤ A, B ≤ N)가 공백을 사이에 두고 주어진다. 이는 A 장면에서 B 장면으로 넘어가는 선택을 할 수 있다는 것을 의미한다. 이때, B에서 저장하는 비용 X는 항상 A에서 저장하는 비용 Y보다 작거나 같다.

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

• 1 ≤ N ≤ 10000
• 1 ≤ K ≤ 5000

• 1 ≤ K ≤ 50

• 추가 제한 없음