You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

给定三个数组 $a, b, c$，它们的长度分别为 $n_a, n_b, n_c$，另外给定一个非负整数 $d$。

请你求出有多少个三元组 $(i, j, k)$ 满足以下两个条件：

1. $a_i \leq b_j \leq c_k$
2. $c_k - a_i \leq d$

这里 $1 \leq i \leq n_a$，$1 \leq j \leq n_b$，$1 \leq k \leq n_c$。

格式

输入格式

第一行包含四个整数 $n_a, n_b, n_c, d$，分别表示数组 $a, b, c$ 的长度以及给定的数 $d$。

第二行包含 $n_a$ 个整数 $a_1, a_2, \dots, a_{n_a}$，表示数组 $a$ 的值。

第三行包含 $n_b$ 个整数 $b_1, b_2, \dots, b_{n_b}$，表示数组 $b$ 的值。

第四行包含 $n_c$ 个整数 $c_1, c_2, \dots, c_{n_c}$，表示数组 $c$ 的值。

输出格式

输出一行一个整数，表示满足条件的三元组 $(i, j, k)$ 的数量。

样例

样例输入 #1

2 2 2 2
1 2
2 3
3 4

样例输出 #1

6

样例解释 #1

在这个样例中，$n_a=2, n_b=2, n_c=2, d=2$。 我们需要寻找满足 $a_i \leq b_j \leq c_k$ 且 $c_k - a_i \leq 2$ 的三元组 $(i, j, k)$：

• $(1, 1, 1)$：$a_1=1, b_1=2, c_1=3$。满足 $1 \leq 2 \leq 3$，且 $3 - 1 = 2 \leq 2$。
• $(1, 2, 1)$：$a_1=1, b_2=3, c_1=3$。满足 $1 \leq 3 \leq 3$，且 $3 - 1 = 2 \leq 2$。
• $(1, 1, 2)$：$a_1=1, b_1=2, c_2=4$。满足 $1 \leq 2 \leq 4$，但 $4 - 1 = 3 > 2$，不满足。
• $(1, 2, 2)$：$a_1=1, b_2=3, c_2=4$。满足 $1 \leq 3 \leq 4$，但 $4 - 1 = 3 > 2$，不满足。
• $(2, 1, 1)$：$a_2=2, b_1=2, c_1=3$。满足 $2 \leq 2 \leq 3$，且 $3 - 2 = 1 \leq 2$。
• $(2, 2, 1)$：$a_2=2, b_2=3, c_1=3$。满足 $2 \leq 3 \leq 3$，且 $3 - 2 = 1 \leq 2$。
• $(2, 1, 2)$：$a_2=2, b_1=2, c_2=4$。满足 $2 \leq 2 \leq 4$，且 $4 - 2 = 2 \leq 2$。
• $(2, 2, 2)$：$a_2=2, b_2=3, c_2=4$。满足 $2 \leq 3 \leq 4$，且 $4 - 2 = 2 \leq 2$。

共有 $6$ 个三元组满足条件，因此输出 6。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \leq n_a, n_b, n_c \leq 2 \times 10^5$，$0 \leq d \leq 10^9$，$1 \leq a_i, b_j, c_k \leq 10^9$。