Hongjun's matrix

Time limit2sMemory limit512 MB

Summary

Given sequences A and B of length N, find the K-th smallest value among all N^2 products A_i * B_j.

Level: Medium7 of 10
Topics: Binary search, Sorting, Math, Two pointers
Solved: No attempts yet

Problem

Hongjun has two sequences $A$ and $B$ , each of length $N$ . He builds an $N \times N$ matrix whose entry in row $i$ and column $j$ is $A_i \times B_j$ .

Hongjun sorts all $N^2$ entries in non-decreasing order and wants to know the value that lands in position $K$ . Positions are counted from 1, and a value that appears several times is counted once for each entry that produces it. Write the program that finds the $K$ -th value for him, since sorting is slow for Hongjun.

Input

The first line contains $N$ and $K$ , separated by a space. ( $1 \le N \le 30000$ , $1 \le K \le N^2$ )

The second line contains the $N$ elements of the sequence $A$ , separated by spaces.

The third line contains the $N$ elements of the sequence $B$ , separated by spaces.

Every element of both sequences is an integer between $1$ and $10^9$ .

Output

Print the $K$ -th smallest entry of the matrix.

Examples2

Example 1
Input
```
2 3
2 3
3 5
```
Expected output
```
10
```
Example 2
Input
```
3 5
2 2 2
3 3 3
```
Expected output
```
6
```