네모네모

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

요약

가로 M, 세로 1인 격자에 막힌 칸을 피해 순서대로 N개의 블록을 놓을 때, 모든 배치에서 항상 블록이 놓이는 칸의 수를 구한다.

문제

네모네모, 네모네모 sign 삐뚤빼뚤해 like

재우는 네모 네모 게임이라는 게임을 즐겨 한다.

네모 네모 게임은 가로 $M$ 칸, 세로 $1$ 칸의 격자판 위에 $N$ 개의 블록을 놓는 게임이다.

격자의 각 칸은 비어 있거나 X 표시가 되어 있다. X 표시가 되어 있는 칸 위에는 블록을 놓을 수 없다.

$i$ 번째 블록은 격자 위 가로로 $A\_i$ 칸, 세로로 $1$ 칸의 공간을 차지한다.

또한, 블록은 순서대로 왼쪽부터 배치해야 한다. 즉, $i$ 번째 블록은 $i-1$ 번째 블록의 오른쪽에 놓여야 한다.

블록은 겹칠 수 없다. 즉, 한 칸의 격자 위에는 최대 한 개의 블록만이 놓일 수 있다.

이러한 조건을 만족하면서 $N$ 개의 블록을 모두 격자판 위에 올릴 경우 게임에서 승리한다.

이 게임에서 승리하도록 블록을 배치하는 경우의 수는 매우 많다. 재우는 이 게임을 좀 더 고능하게 하기 위해서 항상 블록이 놓이는 칸들을 구하려고 한다.

재우를 대신하여 항상 블록이 놓이는 칸의 개수를 구해주자.

첫 번째 줄에 블록 개수 $N$ , 격자판의 가로 길이 $M$ , X 표시된 칸의 수 $K$ 가 공백으로 구분되어 주어진다.

두 번째 줄에 각 블록의 가로 길이를 나타내는 $N$ 개의 정수 $A\_1, A\_2, \cdots , A\_N$ 가 공백으로 구분되어 주어진다.

세 번째 줄에 X 표시된 칸들의 번호를 나타내는 $K$ 개의 정수 $X\_1, X\_2, \cdots , X\_K$ ( $i < j$ 이면 $X\_i < X\_j$ )가 공백으로 구분되어 주어진다.

항상 조건을 만족하도록 블록을 배치할 방법이 있는 입력만 주어진다.

첫 번째 줄에 항상 블록이 놓이는 칸의 개수를 출력한다.