Minimum Jumps on a Board Avoiding Traps

You are given a board with N cells numbered from 1 to N. You start at cell 1 and want to reach cell N with the minimum number of jumps. You are provided with P possible jump lengths and there are T traps located on certain cells. You cannot land on a trap.

Formally, let the cells be numbered 1 through \(N\). You are given an array of allowed jump lengths \(j_1, j_2, \ldots, j_P\) and an array of trap positions. Starting at cell 1, you can jump from cell \(i\) to cell \(i+j_k\) for any allowed jump \(j_k\), as long as \(i+j_k \le N\) and cell \(i+j_k\) is not a trap. If cell \(N\) is a trap, then reaching the end is impossible. Your task is to compute the minimum number of jumps required to reach cell \(N\), or output -1 if it is impossible.

Note: If a jump would land beyond cell \(N\), it is not allowed.

inputFormat

The input is read from stdin and consists of three parts:

1. The first line contains three integers \(N\), \(P\), and \(T\) separated by spaces.
2. The second line contains \(P\) space-separated integers representing the allowed jump lengths.
3. The third line contains \(T\) space-separated integers representing the trap positions. If \(T = 0\), this line will be empty.

Constraints:

• \(1 \leq N \leq 10^5\)
• \(1 \leq P \leq 100\)
• \(0 \leq T \leq N\)

outputFormat

Output to stdout a single integer: the minimum number of jumps required to reach cell \(N\). If it is impossible, output -1.

## sample

10 3 2
2 3 5
3 6

3

</p>