15908번 - 복구

shake! 회사에서는 사용자 목록을 자체 개발한 특별한 방법으로 저장한다. 이 방법을 알고 있는 사람은 세계에 단 두 명밖에 없었지만, 최근 Acka가 shake! 회사를 해킹하여 방법을 세상에 공개하였다.

그 방법은 각 사용자의 데이터를 양의 정수로 표현한 뒤, 데이터 조각으로 바꿔 이어 붙인 뒤 파일에 저장하는 것이다. 각 데이터 조각은 맨 앞에 데이터 조각의 길이를 적고, 나머지 부분에 양의 정수로 표현한 데이터를 적는 것으로 만든다.

예를 들어, 3명의 사용자가 있고, 각 사용자의 데이터가 {2, 5, 5}, {1, 4, 5, 1}, {2, 3, 1}이라고 해 보자. 각각을 데이터 조각으로 바꾸면 {4, 2, 5, 5}, {5, 1, 4, 5, 1}, {4, 2, 3, 1}이 되고, 최종적으로 데이터 조각을 이어 붙여 {4, 2, 5, 5, 5, 1, 4, 5, 1, 4, 2, 3, 1}을 파일에 저장한다.

그런데 Acka가 해킹하는 과정에서 사용자 목록을 저장한 파일을 훼손할 수 있기 때문에, 사용자 목록 파일에 원래는 있어야 하지 말아야 할 수들이 추가되었을 수 있다. shake! 회사에서는 사용자 목록을 복구하기 위해 각 수가 원래의 사용자 목록에도 있었을 가능성을 모두 계산하였으나, 원래의 파일을 복구하는 데에는 실패했다.

이제, shake! 회사의 유능한 직원인 당신이 원래의 파일을 복구해야 한다. 손상된 파일과 각 수가 원래의 사용자 목록에도 있었을 가능성이 주어질 때, 수를 적당히 지워서 올바른 파일로 복구하되, 지운 수들의 가능성의 최댓값을 최소화하여라.

첫 줄에 손상된 파일을 이루는 수의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.

다음 줄에 손상된 파일을 이루는 정수 N개가 주어진다. 이 수들은 모두 1 이상 N 이하이다.

다음 줄에 각 수가 원래의 사용자 목록에도 있었을 가능성을 나타내는 정수 N개가 주어진다. 이 수들은 모두 1 이상 100,000 이하이다.

첫 줄에 지운 수들의 가능성의 최댓값을 최소화했을 때, 지운 수들의 가능성의 최댓값을 출력한다.

만약 수를 지우지 않아도 된다면 0을 출력한다.

예제 1에 대해, 3번째 수와 6번째 수를 지우면 {3, 1, 2}, {2, 1}, {3, 1, 3}이 된다.

예제 2에 대해, 1번째, 8번째, 9번째, 11번째, 16번째, 17번째, 19번째 수를 지우면 {4, 2, 5, 5}, {5, 1, 4, 5, 1}, {4, 2, 5, 2}가 된다.

예제 3에 대해, 수를 지우지 않아도 {5, 5, 5, 5, 5}, {4, 4, 4, 4}, {3, 3, 3}, {2, 2}, {1}이 된다.