Jaewoo enjoys playing a game called the "Nemo Nemo Game." The rules of this game are as follows:

1. A grid of width $M$ arranged in a single row is given.
2. Each cell is either empty or marked with an 'X'. Blocks cannot be placed on cells marked with 'X'. The given $X_i$ values represent the positions of the cells marked with 'X'.
3. There are $N$ blocks, and the horizontal lengths of each block are $A_1, A_2, \dots, A_N$, respectively.
4. Blocks must be placed in order from left to right while satisfying the given conditions.

There are many possible ways to arrange the blocks in this game. To play the game skillfully, Jaewoo wants to find the cells that are always covered by a block regardless of the valid arrangement.

Help Jaewoo find the number of cells that are always covered by a block.

Subtasks

1. $1 \le N, K \le 10$, $1 \le M \le 10$
2. $A_i = 1$
3. $1 \le N, K \le 10^3$, $1 \le M \le 10^3$
4. $2 \le M \le 10^6$
5. No additional constraints

Input

The first line contains the number of blocks $N$, the width of the grid $M$, and the number of cells marked with X, $K$, separated by spaces.

The second line contains $N$ integers $A_1, A_2, \dots, A_N$ representing the horizontal lengths of each block, separated by spaces.

The third line contains $K$ integers $X_1, X_2, \dots, X_K$ representing the positions of the cells marked with X, separated by spaces.

It is guaranteed that the input always allows for at least one valid way to place the blocks.

• $1 \le N, K \le 10^6$
• $2 \le M \le 10^9$
• $1 \le A_i \le 10^9$
• $1 \le X_i \le M$
• $(\sum_{i=1}^N A_i) + K \le M$

Output

Output the number of cells that are always covered by a block on the first line.

Examples

Input 1

2 6 1
2 2
3

Output 1

3

Input 2

4 10 1
1 1 3 3
7

Output 2

5

Input 3

5 11 3
1 1 1 1 1
4 5 11

Output 3

0