Security Vulnerability Patch

Dadas manages a project that depends on many packages. The dependency structure is given as a tree rooted at vertex $1$. Vertex $1$ represents the project itself, and every other vertex represents a package.

Some packages may have security vulnerabilities. You may perform the following two operations.

• Normal patch: Patch a vulnerable package $v$. This costs $C_v$ and fixes only the vulnerability at $v$.
• --force patch: Force-update package $v$. This costs $F_v$ and fixes every vulnerability at and all descendants of . This operation may be performed even if itself is not vulnerable.

The affected vertices of every operation are determined by the original tree. Operations do not change the tree structure or any cost, create new vulnerabilities, or restore vulnerabilities that have already been fixed.

At most $K$ --force patches may be performed. There is no limit on the number of normal patches. No operation may be performed on vertex $1$.

Find the minimum total cost required to fix all vulnerabilities.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, print the minimum total cost required to fix all vulnerabilities on one line.

• $1 \leq T \leq 10\,000$.
• $2 \leq N \leq 100\,000$.
• $0\le K$.