Description

The inevitable day still came. Little F stared blankly at the night sky.

The sky was empty, with not a single star—probably because of the heavy clouds that would not disperse.

As for the clouds in the heart that will not disperse, just let them be. After all, there is no chance to change anything.

Little C brought a long string of star-shaped mini bulbs, pretending they were stars, and handed it to Little F, hoping to cheer him up. However, due to a bit of OCD, Little F noticed that among the total of $n$ bulbs, $k$ bulbs on the string were not lit. Little F decided to work with Little C to light up the entire string.

But perhaps due to clumsiness, Little F could only flip the states of a contiguous segment of bulbs—turning off lit bulbs and turning on unlit bulbs. After some trials, Little F found that he could flip segments of $m$ different lengths.

Little C and Little F eventually spent a very very very very very very long time to light up all the bulbs. They want to know if they were being silly, so they came to you to calculate: in the optimal case, what is the minimum number of operations needed to light up the entire bulb string?

Input Format

Read from standard input.

• The first line contains three positive integers $n$, $k$, $m$.
• The second line contains $k$ positive integers. The $i$-th number is the position $a_i$ of the $i$-th bulb that is not lit.
• The third line contains $m$ positive integers. The $i$-th number is the length $b_i$ of the $i$-th operation.

It is guaranteed that all $b_i$ are distinct; for $1 \le i < k$, $a_i < a_{i+1}$; and the input has a solution.

Output Format

Print one non-negative integer: the minimum number of operations.

5 2 2 
1 5 
3 4

2   

Hint

[Explanation for Sample 1]

[Constraints and Conventions]

Subtasks specify some properties of the testdata. If you find the problem difficult, you may try to solve only part of the testdata.

The data scale and features of each test point are summarized in the table below.

Special property: It is guaranteed that the answer is less than $4$.

Translated by ChatGPT 5