시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB23121152.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$일 이내에 「보스 슬레이어」 칭호를 얻을 수 있는 플레이어 수의 최댓값을 출력한다.

예제 입력 1

3 2 2
1 2 3
0 1 0
2 3

예제 출력 1

7

예제 입력 2

5 3 2
2 5 3 4 5
0 0 2 2 4
1 3 5

예제 출력 2

7
W3sicHJvYmxlbV9pZCI6IjM1NDc3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiVURQQyBcdWM2MjhcdWI3N2NcdWM3NzggXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2MjRcdWIyOThcdWM3NDAgVURQQyBcdWM2MjhcdWI3N2NcdWM3NzggXHVhYzhjXHVjNzg0XHVjNzc0IFx1YzgxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM2MjRcdWQ1MDhcdWQ1NThcdWIyOTQgXHViMGEwXHVjNzc0XHViMmU0ISBVRFBDIFx1YzYyOFx1Yjc3Y1x1Yzc3OFx1YzVkMFx1YjI5NCBcdWNkMWQgJE4kXHVhYzFjXHVjNzU4IFx1YjM1OFx1YzgwNFx1Yzc3NCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWMwMSBcdWIzNThcdWM4MDRcdWM3NDAgXHVkNTU4XHViOGU4XHVjNWQwIFx1ZDA3NFx1YjlhY1x1YzViNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Yzc3OFx1YzZkMFx1Yzc3NCBcdWM4MTVcdWQ1NzRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFkNmNcdWNjYjRcdWM4MDFcdWM3M2NcdWI4NWMsICQxXFxsZXEgaVxcbGVxIE4kXHVjNWQwIFx1YjMwMFx1ZDU3NCwgJGkkXHViYzg4IFx1YjM1OFx1YzgwNFx1Yzc0MCBcdWQ1NThcdWI4ZThcdWM1ZDAgXHVjZDVjXHViMzAwICRBX2kkXHViYTg1XHVjNzU4IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjljYyBcdWQwNzRcdWI5YWNcdWM1YjRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHViOGU4IFx1YzIxOFx1YzZhOSBcdWM3NzhcdWM2ZDBcdWM3NzQgXHVhZjQ5IFx1Y2MyOFx1YmE3NCwgXHVhZGY4XHViMGEwXHVjNzQwIFx1YjM1NFx1Yzc3NFx1YzBjMSBcdWIyZTRcdWI5NzggXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwICRpJFx1YmM4OCBcdWIzNThcdWM4MDRcdWM3NDQgXHVkMDc0XHViOWFjXHVjNWI0XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YjYxMFx1ZDU1YywgXHVkNTVjIFx1YmE4NVx1Yzc1OCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHVkNTU4XHViOGU4XHVjNWQwIFx1Y2Q1Y1x1YjMwMCBcdWQ1NWMgXHVhYzFjXHVjNzU4IFx1YjM1OFx1YzgwNFx1YjljYyBcdWQwNzRcdWI5YWNcdWM1YjRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YjM1OFx1YzgwNFx1YzVkMFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkNTVjIFx1YWMxY1x1Yzc1OCBcdWMxMjBcdWQ1ODkgXHViMzU4XHVjODA0XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWMxMjBcdWQ1ODkgXHViMzU4XHVjODA0XHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjAsIFx1ZDU3NFx1YjJmOSBcdWMxMjBcdWQ1ODkgXHViMzU4XHVjODA0XHVjNzQ0IFx1ZDA3NFx1YjlhY1x1YzViNFx1ZDU1YyBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWI5Y2MgXHViM2M0XHVjODA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjJlOCwgXHVjNWI0XHViNWE0IFx1YjM1OFx1YzgwNFx1YjNjNCBcdWM3OTBcdWFlMzAgXHVjNzkwXHVjMmUwXHVjNzQ0IFx1YzEyMFx1ZDU4OSBcdWIzNThcdWM4MDRcdWM3M2NcdWI4NWMgXHVhYzAwXHVjOWMwXHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3MCwgXHViYWE4XHViNGUwIFx1YjM1OFx1YzgwNFx1Yzc0MCBcdWM4MDFcdWM4MDhcdWQ1NWMgXHVjMjFjXHVjMTFjXHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWIzYzRcdWM4MDRcdWQ1ODhcdWM3NDQgXHViNTRjIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWQwNzRcdWI5YWNcdWM1YjRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFkNmNcdWM4NzBcdWM3ODRcdWM3NzQgXHViY2Y0XHVjN2E1XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MDRcdWNjYjQgXHViMzU4XHVjODA0IFx1YzkxMSAkTSRcdWFjMWNcdWIyOTQgXHVkMmI5XHViY2M0XHVkNTVjIFx1YmNmNFx1YzJhNCBcdWIzNThcdWM4MDRcdWM3NzRcdWIyZTQuIFx1YmNmNFx1YzJhNCBcdWIzNThcdWM4MDQgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjc3Y1x1YjNjNCBcdWQwNzRcdWI5YWNcdWM1YjRcdWQ1NWMgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IFx1MzAwYzxzdHJvbmc+XHViY2Y0XHVjMmE0IFx1YzJhY1x1YjgwOFx1Yzc3NFx1YzViNDxcL3N0cm9uZz5cdTMwMGRcdWI3N2NcdWIyOTQgXHVjZTZkXHVkNjM4XHViOTdjIFx1YzViYlx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1ZDU1YyBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHViY2Y0XHVjMmE0IFx1YjM1OFx1YzgwNFx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YWU2OFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWNlNmRcdWQ2MzhcdWIyOTQgXHVkNTVjIFx1YmM4OFx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWM2MjRcdWQ1MDhcdWQ1NWMgXHVjNjI0XHViMjk4XHViZDgwXHVkMTMwICRLJFx1Yzc3YyBcdWM3NzRcdWIwYjRcdWM1ZDAgXHUzMDBjPHN0cm9uZz5cdWJjZjRcdWMyYTQgXHVjMmFjXHViODA4XHVjNzc0XHVjNWI0PFwvc3Ryb25nPlx1MzAwZCBcdWNlNmRcdWQ2MzhcdWI5N2MgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0IFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzNThcdWM4MDRcdWM3NTggXHVhYzFjXHVjMjE4ICROJCwgXHViY2Y0XHVjMmE0IFx1YjM1OFx1YzgwNFx1Yzc1OCBcdWFjMWNcdWMyMTggJE0kLCBcdWNlNmRcdWQ2MzhcdWI5N2MgXHVkNjhkXHViNGRkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZTMwXHVhYzA0XHVjNzU4IFx1YWUzOFx1Yzc3NCAkSyRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMVxcbGVxIE1cXGxlcSBOXFxsZXEgMjAwXFwsMDAwJDskMVxcbGVxIEtcXGxlcSAxXFwsMDAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ1NThcdWI4ZThcdWM1ZDAgJGkkXHViYzg4IFx1YjM1OFx1YzgwNFx1Yzc0NCBcdWQwNzRcdWI5YWNcdWM1YjRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWM3NTggXHVjMjE4ICRBXzEsIEFfMiwgXFxjZG90cywgQV9OJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxXFxsZXEgQV9pXFxsZXEgMVxcLDAwMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDAgJGkkXHViYzg4IFx1YjM1OFx1YzgwNFx1Yzc1OCBcdWMxMjBcdWQ1ODkgXHViMzU4XHVjODA0XHVjNzU4IFx1YjM1OFx1YzgwNCBcdWJjODhcdWQ2MzggJEJfMSwgQl8yLCBcXGNkb3RzLCBCX04kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkQl9pID0gMCRcdWM3NDAgJGkkXHViYzg4IFx1YjM1OFx1YzgwNFx1Yzc1OCBcdWMxMjBcdWQ1ODkgXHViMzU4XHVjODA0XHVjNzc0IFx1YzVjNlx1Yzc0Y1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuICQoMFxcbGVxIEJfaVxcbGVxIE4pJDxcL3A+XHJcblxyXG48cD5cdWIxMzdcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggJE0kXHVhYzFjXHVjNzU4IFx1YmNmNFx1YzJhNCBcdWIzNThcdWM4MDRcdWM3NTggXHViYzg4XHVkNjM4ICRDXzEsIENfMiwgXFxjZG90cywgQ19NJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxXFxsZXEgQ19pXFxsZXEgTikkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjOGNcdWM3ODRcdWM3NzQgXHVjMmRjXHVjNzkxXHVkNTVjIFx1YjRhNCAkSyRcdWM3N2MgXHVjNzc0XHViMGI0XHVjNWQwIFx1MzAwYzxzdHJvbmc+XHViY2Y0XHVjMmE0IFx1YzJhY1x1YjgwOFx1Yzc3NFx1YzViNDxcL3N0cm9uZz5cdTMwMGQgXHVjZTZkXHVkNjM4XHViOTdjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNCBcdWMyMThcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzNTQ3NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlVEUEMgT25saW5lIEdhbWUiLCJkZXNjcmlwdGlvbiI6IjxwPlRvZGF5IGlzIHRoZSBncmFuZCBvcGVuaW5nIG9mIHRoZSBVRFBDIE9ubGluZSBnYW1lISBUaGVyZSBhcmUgYSB0b3RhbCBvZiAkTiQgZHVuZ2VvbnMgaW4gVURQQyBPbmxpbmUsIGFuZCBlYWNoIGR1bmdlb24gaGFzIGEgbGltaXQgb24gdGhlIG51bWJlciBvZiBwZW9wbGUgd2hvIGNhbiBjbGVhciBpdCBwZXIgZGF5LiBTcGVjaWZpY2FsbHksIGZvciAkMSBcXGxlcSBpIFxcbGVxIE4kLCB0aGUgJGkkLXRoIGR1bmdlb24gY2FuIGJlIGNsZWFyZWQgYnkgYXQgbW9zdCAkQV9pJCBwbGF5ZXJzIHBlciBkYXkuJm5ic3A7T25jZSB0aGUgZGFpbHkgY2FwYWNpdHkgaXMgcmVhY2hlZCwgbm8gb3RoZXIgcGxheWVycyBjYW4gY2xlYXIgZHVuZ2VvbiAkaSQgb24gdGhhdCBkYXkuIEFsc28sIGEgc2luZ2xlIHBsYXllciBjYW4gY2xlYXIgYXQgbW9zdCBvbmUgZHVuZ2VvbiBwZXIgZGF5LjxcL3A+XHJcblxyXG48cD5FYWNoIGR1bmdlb24gY2FuIGhhdmUgYXQgbW9zdCBvbmUgcHJlcmVxdWlzaXRlIGR1bmdlb24uIElmIGEgZHVuZ2VvbiBoYXMgYSBwcmVyZXF1aXNpdGUsIG9ubHkgcGxheWVycyB3aG8gaGF2ZSBjbGVhcmVkIHRoZSBwcmVyZXF1aXNpdGUgZHVuZ2VvbiBjYW4gY2hhbGxlbmdlIGl0LiBUaGVyZSBhcmUgbm8gZHVuZ2VvbnMgdGhhdCByZXF1aXJlIHRoZW1zZWx2ZXMgYXMgYSBwcmVyZXF1aXNpdGUuIEZ1cnRoZXJtb3JlLCB0aGUgcHJvZ3Jlc3Npb24gaXMgZGVzaWduZWQgc28gdGhhdCBldmVyeSBkdW5nZW9uIGlzIHJlYWNoYWJsZSBhbmQgY2FuIGJlIGNsZWFyZWQgYnkgZm9sbG93aW5nIGEgdmFsaWQgc2VxdWVuY2Ugb2YgY2hhbGxlbmdlcy48XC9wPlxyXG5cclxuPHA+T3V0IG9mIGFsbCB0aGUgZHVuZ2VvbnMsICRNJCBhcmUgc3BlY2lhbCBib3NzIGR1bmdlb25zLiBBbnkgcGxheWVyIHdobyBjbGVhcnMgYXQgbGVhc3Qgb25lIGJvc3MgZHVuZ2VvbiB3aWxsIGVhcm4gdGhlIHRpdGxlIG9mIFx1MzAwYzxzdHJvbmc+Qm9zcyBTbGF5ZXI8XC9zdHJvbmc+XHUzMDBkLiBFdmVuIGlmIGEgcGxheWVyIGNsZWFycyBtdWx0aXBsZSBib3NzIGR1bmdlb25zLCB0aGUgdGl0bGUgaXMgYXdhcmRlZCBvbmx5IG9uY2UuIEZpbmQgdGhlIG1heGltdW0gbnVtYmVyIG9mIHBsYXllcnMgd2hvIGNhbiBlYXJuIHRoZSBcdTMwMGM8c3Ryb25nPkJvc3MgU2xheWVyPFwvc3Ryb25nPlx1MzAwZCB0aXRsZSB3aXRoaW4gJEskIGRheXMgZnJvbSB0b2RheSwgdGhlIG9wZW5pbmcgZGF5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIG51bWJlciBvZiBkdW5nZW9ucyAkTiQsIHRoZSBudW1iZXIgb2YgYm9zcyBkdW5nZW9ucyAkTSQsIGFuZCB0aGUgcGVyaW9kICRLJCBkdXJpbmcgd2hpY2ggdGhlIHRpdGxlIGNhbiBiZSBlYXJuZWQsIHNlcGFyYXRlZCBieSBzcGFjZXMuJm5ic3A7JCgxXFxsZXEgTVxcbGVxIE5cXGxlcSAyMDBcXCwwMDAkOyQxXFxsZXEgS1xcbGVxIDFcXCwwMDBcXCwwMDApJDxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgdGhlIGRhaWx5IG1heGltdW0gcGxheWVyIGNhcGFjaXR5ICRBXzEsIEFfMiwgXFxjZG90cywgQV9OJCBmb3IgZWFjaCBkdW5nZW9uICRpJCwgc2VwYXJhdGVkIGJ5IHNwYWNlcy4gJCgxIFxcbGUgQV9pIFxcbGUgMVxcLDAwMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIHRoZSBwcmVyZXF1aXNpdGUgZHVuZ2VvbiBudW1iZXIgJEJfMSwgQl8yLCBcXGNkb3RzLCBCX04kIGZvciBlYWNoIGR1bmdlb24gJGkkLCBzZXBhcmF0ZWQgYnkgc3BhY2VzLiBJZiB0aGVyZSBpcyBubyBwcmVyZXF1aXNpdGUgZHVuZ2VvbiwgJEJfaT0wJCBpcyBnaXZlbi4gJCgwIFxcbGUgQl9pIFxcbGUgTikkPFwvcD5cclxuXHJcbjxwPlRoZSBmb3VydGggbGluZSBjb250YWlucyB0aGUgZHVuZ2VvbiBudW1iZXJzICRDXzEsIENfMiwmbmJzcDtcXGNkb3RzLCBDX00kIGNvcnJlc3BvbmRpbmcgdG8gdGhlICRNJCBkaXN0aW5jdCBib3NzIGR1bmdlb25zLCBzZXBhcmF0ZWQgYnkgc3BhY2VzLiAkKDEgXFxsZSBDX2kgXFxsZSBOKSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0aGUgbWF4aW11bSBudW1iZXIgb2YgcGxheWVycyB3aG8gY2FuIGVhcm4gdGhlIFx1MzAwYzxzdHJvbmc+Qm9zcyBTbGF5ZXI8XC9zdHJvbmc+XHUzMDBkIHRpdGxlIHdpdGhpbiAkSyQgZGF5cyBmcm9tIHRoZSBzdGFydCBvZiB0aGUgZ2FtZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d