题目描述

你是卷王，选了两门上课时间相同的课，分别编号为 1, 2 。 对于第 i 门课，老师会放 ni 页 ppt ，第 j 页 ppt 会在开区间 (Ai,j, Bi,j) 被放出。保证同一门课的任意两个开区间不交。 为了最大化听课效果，你可以在两个教室反复横跳，横跳所需的时间是 K 。你可以在任意实数时间横跳。 对于第 i 门课的第 j 页 ppt ，只要存在一个非空子区间 (l, r) 严格包含于 (Ai,j, Bi,j) 使得你这段时间在第 i 个教室，就认为你学会了这页 ppt 。 初始时间是 0 ，初始地点是第 1 个教室。求最多可以学会几页 ppt 。

输入格式

第一行三个正整数 n1, n2, K 。 接下来 n1 行，每行两个非负整数 A1,j, B1,j。 接下来 n2 行，每行两个非负整数 A2,j, B2,j 。

输出格式

输出一个数表示答案。

输入样例1

3 1 8 10 20 100 101 20 21 15 25

输出样例1

3

输入样例2

1 5 3 1 100 1 2 2 3 3 4 4 5 5 6

输出样例2

4

数据范围及约束

对于所有数据，保证 1 ≤ ni ≤ 3 × 10^5, 0 ≤ Ai,j < Bi,j ≤ 10^9,0≤k≤10^9

Subtask 1 (20 points) ： ni ≤ 10 。

Subtask 2 (30 points) ： ni,Bi,j ≤ 2000 。

Subtask 3 (25 points) ： ni ≤ 2000, Bi,j − Ai,j ≤ 2K。

Subtask 4 (25 points) ：无特殊限制。