Minimum Operations to Light All Bulbs

On a gloomy night, little F noticed that in a string of n star‐shaped bulbs, k bulbs are off. Little F can only change the state of bulbs by flipping a contiguous segment – turning on an off bulb and turning off an on bulb. However, he is only able to flip segments whose lengths belong to a given set of m allowed lengths. In one operation, you can choose any contiguous segment of bulbs whose length is one of the allowed values, and flip all bulbs in that segment.

The flipping operation can be described mathematically. If you flip a segment starting at position i with length L, you generate a bit mask

\(M = \Bigl(2^{L}-1\Bigr) \ll i\)

and update the state vector s as:

\(s = s \oplus M\)

where \(\oplus\) denotes the bitwise XOR operation. The goal is to turn all bulbs on. If it is impossible to achieve this using the allowed operations, output -1.

Input/Output: See below for details.

inputFormat

The input consists of three parts:

1. The first line contains three integers n, m, and k, where n (\(1 \le n \le 15\)) is the total number of bulbs, m is the number of allowed segment lengths, and k is the number of bulbs that are initially off.
2. The second line contains m space‐separated positive integers representing the allowed segment lengths.
3. The third line contains k distinct space‐separated integers in the range [1, n] which indicate the positions (1-indexed) of the bulbs that are initially off. If k is 0, this line will be empty.

outputFormat

Output a single integer: the minimum number of operations required to turn all bulbs on. If it is impossible to achieve the goal, output -1.

sample

4 2 2
1 2
2 4

2