휴가 나가기

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

요약
선행 업무가 최대 하나인 N개의 업무에서 선행 조건을 지키며 중요도 합이 S 이상이 되는 최소 처리 시간을 구한다.
난이도

보통10점 중 7점

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

문제

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

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

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

입력

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

두 번째 줄에 각 업무의 중요도 w_1,w_2,⋯ ,w_Nw\_1,w\_2,\cdots,w\_N이 공백으로 구분되어 정수로 주어진다. (1≤w_i≤100)(1 \le w\_i \le 100)

세 번째 줄에 각 업무의 처리 시간 t_1,t_2,⋯ ,t_Nt\_1,t\_2,\cdots,t\_N이 공백으로 구분되어 정수로 주어진다. (1≤t_i≤1,000)(1 \le t\_i \le 1\\,000)

네 번째 줄에 각 업무의 선행 업무 번호 p_1,p_2,⋯ ,p_Np\_1,p\_2,\cdots,p\_N이 공백으로 구분되어 정수로 주어진다.선행 업무의 번호가 00이면 선행 업무가 없는 것이다. 00이 아닌 모든 p_ip\_i들은 서로 다르다. (0≤p_i≤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