휴가 나가기

Interview

Time limit1sMemory limit1024 MB

Summary

Given tasks with importance, processing time, and at most one prerequisite each, find the minimum total time to reach importance S.

Level: Medium5 of 10
Topics: Dynamic programming, Tree
Solved: No attempts yet

Problem

Yongbeom wants to finish his backlog of tasks before he leaves for vacation. There is not enough time to finish every task, so he will complete only the important ones and then leave.

There are $N$ pending tasks, numbered from 1 to $N$ . Each task may have at most one prerequisite task, and no two tasks share the same prerequisite. Yongbeom can work on only one task at a time. Each task $i$ has an importance $w_i$ and a processing time $t_i$ . The time spent on a set of tasks is the sum of their processing times.

If there were enough time, Yongbeom could finish every task. Find the minimum time needed for the completed tasks to reach a total importance of at least $S$ .

Input

The first line contains two integers $N$ and $S$ , separated by a space. $(1 \le N \le 1\,000$ , $1 \le S \le 100\,000)$

The second line contains the importance $w_1, w_2, \cdots, w_N$ of each task, separated by spaces. $(1 \le w_i \le 100)$

The third line contains the processing time $t_1, t_2, \cdots, t_N$ of each task, separated by spaces. $(1 \le t_i \le 1\,000)$

The fourth line contains the prerequisite task number $p_1, p_2, \cdots, p_N$ of each task, separated by spaces. If $p_i$ is 0, task $i$ has no prerequisite. All nonzero $p_i$ values are distinct. $(0 \le p_i \le N)$

The input is given only when every task can be completed if enough time is available.

Output

Print the minimum time needed for the total importance of the completed tasks to be at least $S$ . If the total importance of all tasks is less than $S$ , print $-1$ .

Examples2

Example 1

Input

7 7
2 3 1 4 5 1 3
3 4 2 8 6 1 2
0 1 2 0 4 0 0

Expected output

Example 2
Input
```
5 13
2 5 3 1 1
4 2 5 6 3
0 1 2 0 4
```
Expected output
```
-1
```