测试数据来自 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\)的范围。