seuOJ227 - 摸鱼的刀客塔

题目描述

博士，您还有许多事情需要处理。现在还不能休息哦。

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

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

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

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

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

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

输入格式

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

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

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

接下来 kk 行，每行有 22 个正整数 bi,ci(1≤bi,ci≤n)b_i,c_i(1\leq b_i,c_i\leq n)，分别表示在 bib_i 时刻进行检查，若检查不合格则阿米驴将在办公室停留至 cic_i 时刻。数据保证有 bi≤ci<bi+1,1≤i<kb_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,41,2,3,4时刻摸鱼。

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