Building Heights

You put up $N$ new buildings in a row. Number them 1 to $N$ from the left.

The heights obey these limits.

• Every building height is a non-negative integer.
• Building 1 has height 0.
• Two neighboring buildings differ in height by at most $K$.
• Building $X_i$ has height at most $T_i$.

Write a program that finds the height of the tallest building you can put up while every limit holds.

The first line contains $N$ and $K$. ($1 \le N, K \le 10^9$)

The second line contains $M$, the number of buildings that carry a height cap. ($0 \le M \le \min(N, 500)$)

If $M$ is at least 1, the third line contains $X_1, X_2, \dots, X_M$ and the fourth line contains $T_1, T_2, \dots, T_M$, separated by spaces. ($1 \le X_i \le N$, $1 \le T_i \le 10^9$, $X_i < X_{i+1}$) If $M$ is 0, the third and fourth lines are not given.

Print the height of the tallest building you can put up while every limit holds.