33070번 - 기숙사 소등

문제

서울과학고의 기숙사는 $N$개의 방으로 이루어져 있고, 이 $N$개의 방에는 각각 1ドル$번부터 $N$번까지 번호가 붙어 있다. 기숙사에 있는 학생들은 새벽 1시가 되면 소등을 해야 하고, 그렇지 않으면 벌점을 받게 된다. 그런데 기숙사에 알 수 없는 오류가 생겨 특정 조건을 만족해야만 소등을 할 수 있게 되었다.

$i$ (1ドル \le i \le N$)번 방이 소등을 하기 위해서는, 1ドル$번 방부터 $i-1$번 방 중 이미 소등을 완료한 방의 수가 집합 $A$에 속해야 한다. 예컨대, $A = \{1,3,9\}$이고, 1,2,3,4ドル$번 방 중 2,4ドル$번 방만 소등하였다면, 1ドル$번 방부터 4ドル$번 방 중 소등한 방의 수가 2ドル$로 $A$의 원소가 아니므로 5ドル$번 방은 소등할 수 없다.

전체 학생들이 받는 벌점의 수를 최소화하기 위해 가능한 한 많은 방을 소등하고자 한다. 임의의 두 방이 동시에 소등하거나 이미 소등한 방이 다시 전등을 켜는 것은 불가능하다.

처음 1ドル$번 방부터 $N$번 방까지의 소등 여부가 주어질 때, 소등하지 못하는 방의 수의 최솟값을 구하여라.

입력

첫 번째 줄에 기숙사 방의 수 $N,ドル 집합 $A$의 원소 수 $K$가 공백으로 구분되어 주어진다.

두 번째 줄에 집합 $A$의 $K$개의 원소 $A_i$가 공백으로 구분되어 주어진다. $A_i$들은 서로 다름이 보장된다.

세 번째 줄에는 1ドル$번 방부터 $N$번 방까지 각 방의 최초 소등 여부가 공백으로 구분되어 주어진다. $i$번째 방이 최초에 소등되었다면 0ドル$이 주어지고, 최초에 소등되지 않았다면 1ドル$이 주어진다.

출력

첫 번째 줄에 최종적으로 소등하지 못하는 방의 수의 최솟값을 출력한다.

제한

• 1ドル \le K \le N \le 3 \times 10^5$
• 0ドル \le A_i \le N - 1$ $(1 \le i \le K)$
• $A_i \ne A_j$ $(1 \le i < j \le K)$

힌트