Counting Valid Shifts

You are given m intervals \([l_1,r_1], [l_2,r_2], \ldots, [l_m,r_m]\) whose lengths are all distinct, an integer sequence \(a_1,a_2,\ldots,a_n\) of length n, and an integer v. For each integer \(k\) in the range \([1,v]\), you need to determine whether there exists no pair of indices \(i, j\) (with \(1 \le i \le n\) and \(1 \le j \le m\)) such that:

[ a_i + k \in [l_j, r_j] ]

Your task is to count and output the number of \(k\) in \([1,v]\) for which the above condition is satisfied.

Note: All the \(m\) intervals have pairwise distinct lengths, i.e. \(r_j - l_j\) are all distinct.

inputFormat

The first line contains three space-separated integers: \(m\) (the number of intervals), \(n\) (the size of the integer sequence), and \(v\) (the upper bound for \(k\)).

The next \(m\) lines each contain two space-separated integers \(l_j\) and \(r_j\), representing the endpoints of the \(j^{th}\) interval.

The last line contains \(n\) space-separated integers denoting the sequence \(a_1, a_2, \ldots, a_n\).

outputFormat

Output a single integer: the count of integers \(k\) in the range \([1, v]\) such that for every \(a_i\) in the sequence and every interval \([l_j,r_j]\), it holds that \(a_i+k\) does not lie inside \([l_j, r_j]\).

sample

2 3 10
1 3
5 8
1 2 4

3