던전 RPG

던전은 N개의 방으로 이루어진 트리 구조이다. 루트(1번 방)에서 탐험을 시작하며, 초기 체력은 H이다. 각 방에는 몬스터가 있어 입장 시 체력이 damage[i]만큼 감소한다(체력이 0 이하가 되면 진입 불가). 몬스터를 처치하면 exp[i]의 경험치를 얻고 recovery[i]만큼 체력이 회복된다. 자식 방은 부모 방을 클리어한 후에만 진입할 수 있다. 최대 경험치를 구하여라.

입력

첫째 줄에 방 수 N과 초기 체력 H가 주어진다. 다음 N줄에 걸쳐 각 방의 피해량 damage[i], 회복량 recovery[i], 경험치 exp[i]가 주어진다. 마지막으로 N-1줄에 걸쳐 부모-자식 관계(부모 번호 자식 번호)가 주어진다.

출력

획득 가능한 최대 경험치를 출력한다.

제한

• 1 ≤ N ≤ 1000
• 1 ≤ H ≤ 10000
• 1 ≤ damage[i] ≤ 10000
• 0 ≤ recovery[i] ≤ 10000
• 0 ≤ exp[i] ≤ 10000

예제 입력 1

3 10
3 5 5
2 1 8
5 3 10
1 2
1 3

예제 출력 1

23

예제 입력 2

3 20
5 10 5
3 2 10
10 5 20
1 2
2 3

예제 출력 2

35

설명: 예제 1에서 방1(10→7→12,EXP5) 진입 후, 방2(12→10→11,EXP8), 방3(11→6→9,EXP10) 모두 방문 가능. 총 5+8+10=23. 예제 2에서 1→2→3 모두 방문: 5+10+20=35.