题目描述

小巡给你 $m$ 个长度互不相等的区间 $[l_1,r_1], \ldots, [l_m,r_m]$ 、一个长度为 $n$ 的整数序列 $a_1,\ldots,a_n$、和一个整数 $v$。

小巡想让你求有多少个整数 $k\in [1,v]$ 使得不存在整数 $i, j$（$1\le i\le n$、$1\le j\le m$）满足 $a_i+k\in[l_j,r_j]$。

输入格式

第一行，三个正整数 $n,m,v$。

第二行，$n$ 个正整数 $a_1,\ldots,a_n$。

接下来 $m$ 行，每行两个正整数 $l_i,r_i$。

保证任意两个编号不同的区间的长度不相等，即对任意 $\bm{1\leq i<j\leq m}$ 都有 $\bm{r_j-l_j\neq r_i-l_i}$。

输出格式

仅一行，一个整数，表示满足条件的 $k$ 的数量。

样例

3 3 15
1 2 4
2 3 
5 7 
15 114514

4

样例 1 解释

符合条件的 $k$ 有 $7,8,9,10$。

10 5 100
5 10 92 23 1 70 33 45 81 20
2 30
1 4
5 19
5 31
91 93

49

数据范围

本题采用捆绑测试。

对于 $100\%$ 的数据，保证 $1\le n,m,a_i\leq 5\times10^5$，$1\le l_i\le r_i\leq10^{18}$，$1\le v\le 10^{18}$，对任意 $1\leq i<j\leq m$ 都有 $r_j-l_j\neq r_i-l_i$。