슈퍼 관과 개미 먹이

보비는 아침마다 애완 개미에게 먹이를 준다. 개미는 관 시설이 딸린 사육 상자에서 산다. 이 관 시설은 정점이 $N$개인 트리이고, 관 하나가 트리의 간선 하나다. 트리의 루트는 1번 정점이다. 액체는 중력 때문에 부모 정점에서 자식 정점으로만 흐른다.

각 관에는 유량 $X_i$가 있다. 부모 정점에 들어온 액체 가운데 몇 퍼센트가 그 관을 지나 자식 정점으로 흐르는지를 나타내는 값이다. 예를 들어 1번 정점에 액체가 12리터 들어오고 그 아래에 유량이 30인 관과 유량이 70인 관이 하나씩 달려 있으면, 앞의 관에 딸린 자식은 3.6리터를 받고 뒤의 관에 딸린 자식은 8.4리터를 받는다. 같은 정점에서 나가는 관의 유량 합은 항상 100이다.

보비의 관 가운데 일부는 보통 관이 아니다. 지나가는 액체의 양을 제곱하는 초능력이 있는 슈퍼 관이다. 위의 예에서 유량이 30인 관이 슈퍼 관이고 초능력을 켰다면 그 자식은 $3.6^2 = 12.96$리터를 받고, 다른 자식은 그대로 8.4리터를 받는다. 이러면 정점에서 나가는 액체가 들어온 액체보다 많아진다. 슈퍼 관이라고 부르는 이유가 바로 이것이다.

보비는 슈퍼 관마다 초능력을 켜거나 끌 수 있다. 초능력을 끈 슈퍼 관은 보통 관과 똑같이 동작한다.

개미는 자식이 없는 정점, 즉 리프에만 산다. 리프 $i$에 사는 개미를 모두 먹이려면 그 리프가 받는 액체가 $K_i$리터 이상이어야 한다. 보비는 루트에 액체 $L$리터를 부어 개미에게 먹이를 준다. 돈이 넉넉하지 않으니 액체를 되도록 적게 사려고 한다. 모든 리프가 필요한 양을 받게 하는 $L$의 최솟값을 구하라.

입력으로 주어지는 자료에서 답이 되는 $L$은 $2 \cdot 10^9$을 넘지 않는다.

첫째 줄에 정점의 개수 $N$이 주어진다 ($1 \le N \le 1000$).

다음 $N - 1$개 줄에 정수 $A_i$, $B_i$, $X_i$, $T_i$가 주어진다 ($1 \le A_i, B_i \le N$, $1 \le X_i \le 100$, $0 \le T_i \le 1$). $A_i$와 $B_i$는 관이 잇는 두 정점이고, $X_i$는 그 관의 유량, $T_i$는 슈퍼 관인지 여부다. $T_i$가 1이면 슈퍼 관, 0이면 보통 관이다. 액체는 1번 정점에서 멀어지는 쪽으로 흐르므로 두 정점 가운데 1번에 더 가까운 쪽이 부모다. 주어지는 $N - 1$개의 관은 트리를 이룬다.

마지막 줄에 정수 $K_i$가 $N$개 주어진다. $i$번 정점이 리프면 $K_i$는 1 이상 10 이하의 정수이고, 리프가 아니면 $-1$이다.

루트에 부어야 하는 액체의 최소량을 소수점 아래 셋째 자리까지 반올림해서 한 줄에 출력한다. 소수점 아래 자리는 값에 상관없이 항상 세 자리를 적는다. 예를 들어 답이 정확히 8이면 8.000을 출력한다.