← 返回题目列表

AtCoder · arc037_c

C. 十亿平方计算

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

問題文

高桥说,N^2我决定通过“数学计算”来提高我的计算技能。 ”N^2质量计算” N 行 N 准备一个列表。 i 该行最左边的方块的左边是一个数字。 写入 a_i , j 列顶部方块上方是数字。 写入 b_j 。高桥君就在这张桌子上。 i 行 j 在栏中 计算并写入 a_i × b_j 的值。

我太快解决了并且感到无聊,所以高桥君自己写了它。 我决定按升序对 N^2 值进行排序。排序的结果是从最小的开始 查找位于(从数字 K 番目 (1 开始计数)的值。


入力

输入是按以下格式从标准输入给出的。

N K
a_1 a_2 .. a_N
b_1 b_2 .. b_N
  • 1 行显示表中的行数和列数。 N (1 ≦ N ≦ 30000)以及要查找的值的重新排列位置。 K (1 ≦ K ≦ N^2) 用空格分隔。
  • 2 行包含表的每一行。 i (1 ≦ i ≦ N),写入该行最左边方块左侧的数字 a_i (1 ≦ a_i ≦ 10^9) 用空格分隔。
  • 3 行包含表的每一列。 j (1 ≦ j ≦ N),该列顶部单元格上方写的数字 b_j (1 ≦ b_j ≦ 10^9) 用空格分隔。

部分点

针对此问题设置了部分分数。

  • 5 点的测试用例是 1 ≦ N ≦ 10 很满意。 当

出力

Takahashi 将一个表写入标准输出。 当 N^2 值按升序排序时,最小的 输出位于 K 番目 (1 位置的值(从数字开始算),并在末尾换行。


入力例1

2 3
2 3
3 5

出力例1

10

按升序对高桥写入的值进行排序 6, 9, 10, 15 ,从最小的开始 第 3 个值为 10 变为。


入力例2

3 7
1 2 1
2 1 2

出力例2

2

按升序对高桥写入的值进行排序 1, 1, 2, 2, 2, 2, 2, 4, 4 ,从最小的开始 第 7 个值为 2 变为。


入力例3

4 8
701687787 500872619 516391519 599949380
458299111 633119409 377269575 717229869

出力例3

317112176525562171