题目描述

有两组卡片，第一组有 $n$ 张，数值分别为 $a_1,\ldots,a_n$；第二组有 $m$ 张，数值分别为 $b_1,\ldots,b_m$，两组都不保证有序。

从第一组和第二组中各选一张，组成配对 $(i,j)$。给定整数 $L,R$，满足 $L\le R$，请统计有多少个配对满足 $L\le a_i+b_j\le R$。

每张卡片有自己的下标，数值相同但下标不同的卡片仍分别计数。两个配对只要任意一张卡片的下标不同，就视为不同方案。

输入格式

第一行包含四个整数 $n,m,L,R$。

第二行包含 $n$ 个整数，表示第一组卡片数值。

第三行包含 $m$ 个整数，表示第二组卡片数值。

输出格式

输出一个整数，表示符合条件的配对总数。

2 2 4 4
1 2
2 3

2

3 2 0 0
-1 -1 0
1 0

3

样例 1 解释

合法的数值配对是 (1,3) 和 (2,2)，各对应一对卡片，答案为 2。

样例 2 解释

第一组两张值为 -1 的卡片都可以与第二组值为 1 的卡片配对；值为 0 的两张卡片也可以配对，共 3 种。

数据范围与提示

对于所有数据，$1\le n,m\le 200000$，$-10^9\le a_i,b_j\le10^9$，$-2\times10^9\le L\le R\le2\times10^9$。

共 $20$ 个测试点，每个测试点 $5$ 分，按测试点独立计分，总分 $100$ 分。

测试点	规模限制
1—5	$n,m\le 20$
6—10	$n,m\le 2000$
11—15	$n,m\le 50000$
16—20	$n,m\le 200000$

表中的规模限制只限制对应参数的上界，所有测试点同时满足上述完整数据范围。

时间限制：2 秒。内存限制：128 MiB。