만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

휴가 나가기

면접 대비

시간 제한1초메모리 제한1024 MB

요약
각 작업에 선행 작업이 하나씩 있을 때, 중요도 합이 S 이상이 되는 최소 처리 시간을 구합니다.
난이도

보통10점 중 5점

유형
동적 계획법, 트리
정답자
아직 제출이 없습니다

문제

용범이는 휴가를 나가기 전에 밀린 업무를 처리하려고 한다. 하지만 모든 업무를 처리할 시간이 부족해서, 중요한 업무만 골라 처리하고 떠나려고 한다.

밀린 업무는 총 NN개이며, 1번부터 NN번까지 번호가 매겨져 있다. 각 업무에는 선행 업무가 최대 1개 있을 수 있고, 선행 업무는 업무마다 모두 다르다. 용범이는 한 번에 한 업무만 처리할 수 있다. 업무 ii마다 중요도 wiw_i와 처리하는 데 걸리는 시간 tit_i가 주어진다. 업무들을 처리하는 데 걸리는 시간은 처리한 업무들의 처리 시간의 합이다.

시간이 충분하면 용범이는 모든 업무를 처리할 수 있다. 하지만 휴가까지 남은 시간이 얼마 없다. 처리한 업무들의 중요도 합이 SS 이상이 되도록 하는 데 필요한 최소 시간을 구하시오.

입력

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

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

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

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

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

출력

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

예제2

  1. 예제 1

    입력
    7 7
2 3 1 4 5 1 3
3 4 2 8 6 1 2
0 1 2 0 4 0 0
    예상 출력
    9

  2. 예제 2

    입력
    5 13
2 5 3 1 1
4 2 5 6 3
0 1 2 0 4
    예상 출력
    -1