휴가 나가기

휴가가 얼마 남지 않은 용범이는 휴가를 나가기 전에 밀린 업무들을 처리하려고 한다. 그러나 모든 업무를 처리하기에는 시간이 부족하기 때문에 중요한 업무들만 처리하고 나가려고 한다.

용범이가 밀린 업무는 총 $N$개가 있고, $1$번부터 $N$번까지 업무마다 번호가 매겨져 있다. 또한, 각 업무는 해당 업무를 처리하기 전에 먼저 처리해야 하는 선행 업무가 최대 $1$개 있을 수 있으며, 각 업무들의 선행 업무는 모두 다르다. 용범이는 한 번에 한 업무만 처리할 수 있기 때문에, 업무마다 중요도 $w_i$와 처리하는 데 걸리는 시간 $t_i$를 정리하고 어떻게 업무를 처리하는 것이 효율적인지 알아내려고 한다. 업무들을 처리하는 데 걸리는 시간은 처리한 업무들의 처리 시간의 합이다.

충분한 시간이 주어진다면 용범이는 모든 업무를 처리할 수 있지만, 휴가를 나가기까지 시간이 얼마 남지 않았다. 빨리 휴가를 나가고 싶어하는 용범이를 도와 처리한 업무들의 중요도 합이 $S$ 이상이 되게 하는데 필요한 최소 시간을 구해주자.

첫 번째 줄에 업무의 수 $N$과 처리한 업무들의 중요도 합의 최소 $S$가 공백으로 구분되어 정수로 주어진다. $(1 \le N \le 1\,000;$ $1 \le S \le 100\,000)$

두 번째 줄에 각 업무의 중요도 $w_1,w_2,\cdots,w_N$이 공백으로 구분되어 정수로 주어진다. $(1 \le w_i \le 100)$

세 번째 줄에 각 업무의 처리 시간 $t_1,t_2,\cdots,t_N$이 공백으로 구분되어 정수로 주어진다. $(1 \le t_i \le 1\,000)$

네 번째 줄에 각 업무의 선행 업무 번호 $p_1,p_2,\cdots,p_N$이 공백으로 구분되어 정수로 주어진다.선행 업무의 번호가 $0$이면 선행 업무가 없는 것이다. $0$이 아닌 모든 $p_i$들은 서로 다르다. $(0 \le p_i \le N)$

충분한 시간이 주어진다면 모든 업무를 처리할 수 있는 경우만 입력으로 주어진다.

처리한 업무의 중요도의 합이 $S$이상이 되게 하는데 필요한 시간의 최솟값을 출력한다. 만약 모든 업무를 처리해도 중요도의 합이 $S$ 미만이라면 $-1$을 출력한다.