폐쇄 시간

헝가리에는 번호가 $0$부터 $N - 1$까지 매겨진 $N$개의 도시가 있다.

도시들은 번호가 $0$부터 $N - 2$까지 매겨진 $N - 1$개의 양방향 도로로 연결되어 있다. 도로 $j$ ($0 ≤ j ≤ N - 2$)는 도시 $U\[j]$와 도시 $V\[j]$를 잇고, 길이는 $T\[j]$이다. 즉, 이 도로로 두 도시 사이를 이동하는 데 $T\[j]$의 시간이 걸린다. 도로는 서로 다른 두 도시를 잇고, 두 도시 쌍은 많아야 하나의 도로로 연결된다.

서로 다른 두 도시 $a$와 $b$ 사이의 경로는 다음 조건을 만족하는 서로 다른 도시들의 나열 $p_0 , p_1 , \dots , p_l$이다.

• $p_0 = a$
• $p_l = b$
• 모든 $i$ ($0 ≤ i < l$)에 대해 도시 $p_i$와 $p_{i+1}$을 잇는 도로가 있다.

도로를 이용하면 어떤 도시에서든 다른 도시로 이동할 수 있다. 즉, 서로 다른 두 도시 사이에는 항상 경로가 있다. 두 도시를 잇는 경로는 하나뿐이다.

경로 $p_0 , p_1 , \dots, p_t$의 길이는 경로에서 연속한 도시를 잇는 $t$개 도로 길이의 합이다.

헝가리에서는 건국 기념 축제에 참석하려고 많은 사람이 두 주요 도시로 이동한다. 축제가 끝나면 사람들은 집으로 돌아간다. 정부는 인파가 주민들의 생활을 방해하지 않도록 하려고, 정해진 시각에 모든 도시를 봉쇄하기로 했다. 정부는 각 도시에 0 이상의 봉쇄 시각을 정한다. 모든 도시의 봉쇄 시각 합은 $K$를 넘을 수 없다. 정확히는, $0$부터 $N - 1$까지 모든 $i$에 대해 도시 $i$에 배정된 봉쇄 시각 $c\[i]$는 0 이상의 정수이며, 모든 $c\[i]$의 합은 $K$ 이하여야 한다.

도시 $a$와 봉쇄 시각 배정을 생각하자. 도시 $b$가 도시 $a$에서 도달 가능하다는 것은, $b = a$이거나, 두 도시 사이의 경로 $p_0 , \dots , p_t$ (특히 $p_0 = a$, $p_t = b$)가 다음 조건을 모두 만족하는 것이다.

• 경로 $p_0, p_1$의 길이는 $c\[p_1]$ 이하이다.
• 경로 $p_0, p_1, p_2$의 길이는 $c\[p_2]$ 이하이다.
• $\dots$
• 경로 $p_0 , p_1 , p_2 ,\dots , p_t$의 길이는 $c\[p_t]$ 이하이다.

올해 축제의 두 주요 행사장은 도시 $X$와 도시 $Y$에 있다. 봉쇄 시각 배정마다 편의 점수를 다음 두 수의 합으로 정의한다.

• 도시 $X$에서 도달 가능한 도시의 수
• 도시 $Y$에서 도달 가능한 도시의 수

어떤 도시가 $X$에서도 도달 가능하고 $Y$에서도 도달 가능하면, 그 도시는 편의 점수에 두 번 계산된다.

봉쇄 시각을 적절히 배정했을 때 얻을 수 있는 편의 점수의 최댓값을 구하라.

• $2 ≤ N ≤ 200\,000$
• $0 ≤ X < Y < N$
• $0 ≤ K ≤ 10^{18}$
• $0 ≤ U\[j] < V\[j] < N$ ($0 ≤ j ≤ N - 2$인 각 $j$에 대해)
• $1 ≤ W\[j] ≤ 10^6$ ($0 ≤ j ≤ N - 2$인 각 $j$에 대해)
• 도로를 이용해 어떤 도시에서든 다른 도시로 이동할 수 있다.
• $S_N ≤ 200\,000$이며, $S_N$은 각 테스트 케이스에서 max_score를 호출할 때의 $N$ 총합이다.