题目描述

鲁道夫打算去拜访伯纳德，他决定乘坐地铁前往。地铁票可以在售票机上购买，售票机只接受恰好两枚硬币，且这两枚硬币的面额之和不超过 $k$。

鲁道夫有两个口袋装着硬币。左口袋有 $n$ 枚硬币，面额分别为 $b_1, b_2, \dots, b_n$。右口袋有 $m$ 枚硬币，面额分别为 $c_1, c_2, \dots, c_m$。他想要从左口袋中选出一枚硬币，从右口袋中选出一枚硬币（共两枚）。

请你帮助鲁道夫计算，有多少种方法可以选择下标 $f$ 和 $s$，使得 $b_f + c_s \le k$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含三个正整数 $n$、$m$ 和 $k$（$1 \le n, m \le 100, 1 \le k \le 2000$），分别表示左口袋和右口袋中硬币的数量，以及售票机接受的两枚硬币面额之和的最大值。

每个测试用例的第二行包含 $n$ 个整数 $b_i$（$1 \le b_i \le 1000$），表示左口袋中每枚硬币的面额。

每个测试用例的第三行包含 $m$ 个整数 $c_i$（$1 \le c_i \le 1000$），表示右口袋中每枚硬币的面额。

输出格式

对于每个测试用例，输出一个整数，表示鲁道夫可以选择两枚硬币（每个口袋各选一枚），使得它们的面额之和不超过 $k$ 的方案数。

说明/提示

注意，这里的配对是指硬币在数组中的下标对，而不是它们的面额。

在第一个测试用例中，鲁道夫可以选择以下硬币对：$[1, 1], [1, 2], [1, 4], [2, 1], [2, 2], [2, 4]$。

在第二个测试用例中，鲁道夫无法从每个口袋各选一枚硬币，使得它们的面额之和不超过 $k=4$。

在第三个测试用例中，鲁道夫可以选择：$[1, 1], [2, 1], [3, 1], [4, 1]$。

在第四个测试用例中，鲁道夫可以从左口袋和右口袋中任意选择一枚硬币。

由 ChatGPT 4.1 翻译

样例

4
4 4 8
1 5 10 14
2 1 8 1
2 3 4
4 8
1 2 3
4 2 7
1 1 1 1
2 7
3 4 2000
1 1 1
1 1 1 1

6
0
4
12