| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 23 | 12 | 11 | 52.381% |
오늘은 UDPC 온라인 게임이 정식으로 오픈하는 날이다! UDPC 온라인에는 총 $N$개의 던전이 있으며, 각 던전은 하루에 클리어할 수 있는 인원이 정해져 있다. 구체적으로, $1\leq i\leq N$에 대해, $i$번 던전은 하루에 최대 $A_i$명의 플레이어만 클리어할 수 있다. 하루 수용 인원이 꽉 차면, 그날은 더이상 다른 플레이어가 $i$번 던전을 클리어할 수 없다. 또한, 한 명의 플레이어는 하루에 최대 한 개의 던전만 클리어할 수 있다.
각 던전에는 최대 한 개의 선행 던전이 존재할 수 있다. 선행 던전이 있는 경우, 해당 선행 던전을 클리어한 플레이어만 도전할 수 있다. 단, 어떤 던전도 자기 자신을 선행 던전으로 가지지 않으며, 모든 던전은 적절한 순서에 따라 도전했을 때 반드시 클리어할 수 있는 구조임이 보장된다.
전체 던전 중 $M$개는 특별한 보스 던전이다. 보스 던전 중 하나라도 클리어한 플레이어는 「보스 슬레이어」라는 칭호를 얻게 된다. 한 플레이어가 보스 던전을 여러 번 깨더라도 칭호는 한 번만 주어진다. 게임이 오픈한 오늘부터 $K$일 이내에 「보스 슬레이어」 칭호를 얻을 수 있는 플레이어 수의 최댓값을 구해보자.
첫째 줄에 던전의 개수 $N$, 보스 던전의 개수 $M$, 칭호를 획득할 수 있는 기간의 길이 $K$가 공백으로 구분되어 주어진다. $(1\leq M\leq N\leq 200\,000$;$1\leq K\leq 1\,000\,000)$
둘째 줄에 하루에 $i$번 던전을 클리어할 수 있는 플레이어의 수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1\leq A_i\leq 1\,000\,000)$
셋째 줄에 $i$번 던전의 선행 던전의 던전 번호 $B_1, B_2, \cdots, B_N$이 공백으로 구분되어 주어진다. $B_i = 0$은 $i$번 던전의 선행 던전이 없음을 의미한다. $(0\leq B_i\leq N)$
넷째 줄에 서로 다른 $M$개의 보스 던전의 번호 $C_1, C_2, \cdots, C_M$이 공백으로 구분되어 주어진다. $(1\leq C_i\leq N)$
첫째 줄에 게임이 시작한 뒤 $K$일 이내에 「보스 슬레이어」 칭호를 얻을 수 있는 플레이어 수의 최댓값을 출력한다.
3 2 2 1 2 3 0 1 0 2 3
7
5 3 2 2 5 3 4 5 0 0 2 2 4 1 3 5
7