题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$ 和一个长度为 $m$ 的数列 $b_1, b_2, \ldots, b_m$。

你需要构造一个包含 $n \times m$ 个数的二维数列 $c$，其中 $c_{i, j} = a_i \times b_j$。

你需要求出二维数列 $c$ 中从小到大排序后第 $k$ 个元素的数值。

输入格式

第一行，三个整数 $n, m, k$（$1 \le n,m \le 10^5, 1 \le k \le n \times m$）。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(-10^9 \le a_i \le 10^9)$。

第三行，$m$ 个整数 $b_1, b_2, \ldots, b_m(-10^9 \le b_i \le 10^9)$。

输出格式

输出一个整数，表示二维数列 $c$ 中从小到大排序后第 $k$ 个元素的数值。

样例

2 3 4
2 5
3 1 5

10

说明/提示

样例解释

二位数列 $c$ 对应的每个元素为：

$6, 2, 10$
$15, 5, 25$

将这些数从小到大排序后为 $2, 5, 6, 10, 15, 25$，其中第 $4$ 个数为 $10$。

数据规模与约定

• 对于 $20\%$ 的数据，$n,m \le 1000; 0 \le a_i, b_i \le 10^3$
• 对于 $50\%$ 的数据，$n,m \le 10^4; 0 \le a_i, b_i \le 10^6$
• 对于 $100\%$ 的数据，$1 \le n,m \le 10^5; -10^9 \le a_i, b_i \le 10^9; 1 \le k \le n \times m$

注意：对于 $100\%$ 的数据，$a_i, b_i$ 可能是负数。