D. 摸鱼的刀客塔

作为罗德岛的精神领袖，刀客塔被助理阿米驴要求每天 $25$ 小时高强度办公。

刀客塔的一天有 $n$ 个时刻。在每一个时刻中，刀客塔只能处理 $1$ 份文件，并在该时刻的结束处理完这份文件。

同时，他一共会收取 $m$ 次新文件。准确地说，他会在 $t_i$ 时刻的开始收到 $a_i$ 份待处理的文件。

助理阿米驴会安排 $k$ 次检查，每次检查的时刻为 $b_i$。若在 $b_i$ 时刻中，刀客塔未处理完的文件数超过 $w$，那么阿米驴会在 $c_i$ 时刻之前（包含 $c_i$ 时刻）一直在控制中枢督促刀客塔办公；否则阿米驴会立即离开（这种情况下可以认为她在 $b_i$ 时刻不在控制中枢）。

为了节省所剩不多的理智，刀客塔决定在阿米驴不在的时候偷偷摸鱼。他可以选择一些时刻不处理文件（但是仍然会收取新文件），每个不处理文件的时刻记为 $1$ 次摸鱼。

现在，失去理智的刀客塔已经无法完成任何计算了，只好来求助你。请你告诉他他最多能摸鱼多少次，给予他继续工作的动力。

第一行有一个正整数 $T(1\leq T\leq 20)$，表示数据的组数。

对于每组数据，第一行有 $4$ 个正整数 $n(1\leq n\leq 10^9)$，$m,k(1\leq m,k\leq 10^5,1\leq \sum m,\sum k\leq 10^6)$，$w(1\leq w\leq 10^9)$，分别表示 $n$ 个时刻、收取 $m$ 次新文件、安排 $k$ 次检查、对于未处理文件数的限制 $w$。

接下来 $m$ 行，每行有 $2$ 个正整数 $t_i(1\leq t_i\leq n),a_i(1\leq a_i\leq 10^5)$，分别表示在 $t_i$ 时刻收取 $a_i$ 份新文件。数据保证有 $t_i<t_{i+1},1\leq i<m$。

接下来 $k$ 行，每行有 $2$ 个正整数 $b_i,c_i(1\leq b_i,c_i\leq n)$，分别表示在 $b_i$ 时刻进行检查，若检查不合格则阿米驴将在办公室停留至 $c_i$ 时刻。数据保证有 $b_i\leq c_i<b_{i+1},1\leq i<k$。

对于每组数据，输出一个整数，表示刀客塔最多摸鱼多少次。

样例输入

2
5 5 3 10
1 2
2 2
3 1
4 2
5 6
1 1
4 4
5 5
10 3 2 10
1 7
4 4
7 5
4 5
8 10

样例输出

4
6

样例解释

在第一组样例中，刀客塔可以选择在$1,2,3,4$时刻摸鱼。

在第二组样例中，刀客塔可以选择在$2,3,4,5,6,7$时刻摸鱼。