← 返回题目列表

Codeforces · 1941/A

A. 鲁道夫和票

中文机器翻译题面 查看原题

鲁道夫要去拜访伯纳德,他决定乘坐地铁去见他。可以在接受两枚硬币的机器上购买门票,硬币的总和不超过 $$$k$$$。

鲁道夫有两个装有硬币的口袋。左边口袋里有$$$n$$$硬币,面额为$$$b_1、b_2、\dots、b_n$$$。右侧口袋里有 $$$m$$$ 硬币,面额为 $$$c_1、c_2、\dots、c_m$$$。他想从左口袋中恰好选择一枚硬币,并从右口袋中恰好选择一枚硬币(总共两枚硬币)。

帮助 Rudolf 确定有多少种方法来选择索引 $$$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

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

输出 #1

6
0
4
12

注意

请注意,这些对表示数组中硬币的索引,而不是它们的面额。

在第一个测试用例中,Rudolf 可以选择以下硬币对:$$$[1, 1], [1, 2], [1, 4], [2, 1], [2, 2], [2, 4]$$$。

在第二个测试用例中,Rudolf 无法以任何方式从每个口袋中选择一枚硬币,因为第一个和第二个数组中的任何两个元素的总和将超过 $$$k=4$$$ 的值。

在第三个测试用例中,Rudolf 可以选择:$$$[1, 1], [2, 1], [3, 1], [4, 1]$$$。

在第四个测试用例中,鲁道夫可以从左口袋中选择任何硬币,从右口袋中选择任何硬币。