测试数据来自 nnu_contest/1263

第$k$小的乘积

时间限制:1s

空间限制:64MB

题目描述

给定长度为$n$的正项数列$a,b$，在$a,b$两个数列中各取一个数$a_i,b_j$并将它们相乘，可以得到一个乘积。问$a_i*b_j$这共$n^2$个乘积中，第$k$小的数是多少？

输入格式

第一行两个整数$n,k$，表示数列长度和要查询的排名$(第k小)$。。

接下来两行每行$n$个整数，表示$a,b$两个正项数列。

输出格式

一个整数，表示答案。

样例输入1

2 2
1 2 
5 4 

样例输出1

5

样例1解释

四个乘积分别为: 5 4 10 8

最小的是4，第二小的是5，所以答案填5

样例输入2

3 2
1 1 1
2 4 10

样例输出2

2

样例2解释

乘积按大小排名分别是：2,2,2,4,4,4,10,10,10

排在第二位的是2

样例输入3

10 12
2 5 12 2 45 6 23 4 5 8 
6 1 23 5 21 27 32 11 4 3 

样例输出3

10

数据范围及限制

$1\le n\le 10^5,1\le k\le n^2,1\le a_i,b_i\le 10^9$

请注意：两个数的乘积可能超出$int$的范围。