AT_arc037_c.[ARC037C] 億マス計算

高桥君决定通过“N²格计算”来提升自己的计算能力。“N²格计算”是指准备一个 $N$ 行 $N$ 列的表格进行计算。在第 $i$ 行的最左侧格子的左边写有数字 $a_i$，在第 $j$ 列的最上方格子的上方写有数字 $b_j$。高桥君会在这个表格的第 $i$ 行第 $j$ 列格子中写下 $a_i \times b_j$ 的值。

很快他就完成了所有计算，觉得有些无聊，于是决定将自己写下的 $N^2$ 个值按升序排列。请你求出排序后从小到大第 $K$ 个（从 $1$ 开始计数）值是多少。

输入通过标准输入给出，格式如下：

$N$ $K$ $a_1$ $a_2$ ... $a_N$ $b_1$ $b_2$ ... $b_N$

• 第 $1$ 行包含表格的行数和列数 $N$（$1 \leq N \leq 30000$），以及要求的排序后第 $K$ 个值的位置 $K$（$1 \leq K \leq N^2$），以空格分隔。
• 第 $2$ 行包含每一行左侧写的数字 $a_i$（$1 \leq a_i \leq 10^9$），共 $N$ 个，以空格分隔。
• 第 $3$ 行包含每一列上方写的数字 $b_j$（$1 \leq b_j \leq 10^9$），共 $N$ 个，以空格分隔。

请输出高桥君在表格中写下的 $N^2$ 个值按升序排列后从小到大第 $K$ 个（从 $1$ 开始计数）值，并换行。

部分分

本题设有部分分。

• 满足 $1 \leq N \leq 10$ 的测试点占 $5$ 分。

样例解释 1

将高桥君写下的值按升序排列后为 $6,\ 9,\ 10,\ 15$，从小到大第 $3$ 个值为 $10$。

样例解释 2

将高桥君写下的值按升序排列后为 $1,\ 1,\ 2,\ 2,\ 2,\ 2,\ 2,\ 4,\ 4$，从小到大第 $7$ 个值为 $2$。

由 ChatGPT 4.1 翻译