hackercupai/hackercup huggingface dataset:
Melody is planning her Christmas vacation in the Metalverse, an ore-rich VR experience consisting of \(T\) virtual worlds.

A given world has \(N\) cities (numbered from \(1\) to \(N\)) with \(N - 1\) roads running between them. The \(i\)th road allows Melody to drive between cities \(P_i\) and \(i+1\) in either direction (with \(1 \le P_i \le i\)). City \(i\) also contains \(C_i\) ore-naments which Melody can collect as souvenirs while she's there.

Melody's vacation consists of starting in any city of her choice, and then repeatedly performing either of the following actions:

1. Drive along a road to another city, unless her previous action was to drive *from* that city
2. Teleport to any other city

Melody may visit a city multiple times, but may only collect its ore-naments once. She may stop her vacation at any point.

Please help Melody evaluate, for each world, the minimum number of times she must teleport to collect at least K ore-naments, if it's possible at all.

# Constraints

\(1 \le T \le 95\)
\(2 \le N \le 10^6\)
\(1 \le K \le 10^{12}\)
\(0 \le C_i \le 10^9\)
\(1 \le P_i \le i\)

The sum of \(N\) across all worlds is at most \(5{,}000{,}000\).

# Input

Input begins with an integer \(T\), the number of virtual worlds to be evaluated. For each world, there is first a line containing \(2\) space-separated integers, \(N\) and \(K\). Then, there is a line containing \(N\) space-separated integers, \(C_{1..N}\). Then, there is a line containing \(N-1\) space-separated integers, \(P_{1..(N-1)}\).

# Output

For the \(i\)th world, print a line containing *"Case #i: "* followed a single integer, the minimum number of times Melody must teleport to collect at least \(K\) ore-naments, or \(-1\) if it's impossible to do so.

# Sample Explanation

In the first three worlds, the cities are arranged as follows:

{{PHOTO_ID:2893643357566792|WIDTH:300}}

In the first world, one option is to start in city \(4\), drive to city \(2\), and finally drive to city \(3\). This will yield \(40 + 20 + 30 = 90\) ore-naments.

In the second world, one option is to start in city \(2\), drive to city \(1\), teleport to city \(3\), drive to city \(2\), and finally drive to city \(4\). This will yield \(20 + 10 + 30 + 0 + 40 = 100\) ore-naments.