题目描述

现在有一排\(N\)个鱼缸，每个鱼缸的高度都是\(W\)，第\(i\)个鱼缸里水的高度为\(H_i\)，保证\(H_i \lt W\)。

现在放入\(M\)条鱼，第\(i\)条鱼被放入第\(P_i\)个鱼缸，同时它最多能跳\(J_i\)单位。鱼\(i\)能从鱼缸\(a\)跳到鱼缸\(b\)当且仅当\(|a-b|\leq 1\)且\(J_i \gt W-H_a\)。

现在每条鱼开始寻找伙伴，它们开始跳，直到跳某个鱼缸然后停下。等所有鱼都停下了，处在同一鱼缸的鱼就会相互认识。求此时相互认识的鱼的对数的最大值。

格式

输入格式

第一行三个整数表示\(N,M,W\)。

第二行\(N\)个整数表示\(H_{1..N}\)。

接下来\(M\)行，第\(i\)行两个整数表示\(P_i,J_i\)

输出格式

一个数表示答案。

样例1

样例输入1

3 4 5
4 2 3
1 1
3 3
2 3
1 7

样例输出1

3

样例解释

鱼\(1\)由于\(J_1 \leq W - H_1\)因此只能留在鱼缸\(1\)。

类似的，鱼\(3\)由于\(J_3 \leq W-H_2\)因此只能留在鱼缸\(2\)。

令鱼\(4\)跳到鱼缸\(2\)，鱼\(2\)跳到鱼缸\(2\)，然后令所有鱼停下，此时鱼\(2,3,4\)两两认识，对数达到\(3\)，可以证明这是最大值。

限制

对于所有数据，\(2\leq N \leq 2×10^4,1 \leq M \leq 200,1 \leq W \leq 2×10^6,1\leq H_i \leq 10^6,1\leq P_i\leq N,1\leq J_i \leq 10^6\)。

测试点编号	\(n\)	\(m\)	\(H_i\)
\(1\)	无额外限制	无额外限制	\(H_i\)全部相同
\(2,3,4,5,6\)	\(N \le 20\)	\(M \le 20\)	无额外限制
\(7,8,9,10\)	\(N \le 50\)	\(M \le 50\)	无额外限制
\(11,12,13,14\)	无额外限制	\(M \le 50\)	无额外限制
\(15,16,17,18\)	无额外限制	无额外限制	无额外限制