홍준이의 행렬

시간 제한2초메모리 제한512 MB

요약

길이 N인 두 수열 A와 B가 주어질 때, N^2개의 곱 A_i * B_j 중 K번째로 작은 값을 찾는다.

난이도: 보통10점 중 7점
유형: 이분 탐색, 정렬, 수학, 투 포인터
정답자: 아직 제출이 없습니다

문제

홍준이에게 길이가 $N$ 인 수열 $A$ 와 $B$ 가 있다. 홍준이는 이 두 수열로 $N \times N$ 행렬을 만들었다. 행렬의 $i$ 행 $j$ 열 원소는 $A_i \times B_j$ 이다.

홍준이는 행렬의 원소 $N^2$ 개를 모두 오름차순으로 정렬한 다음, 앞에서 $K$ 번째에 오는 값이 무엇인지 알고 싶다. 순서는 1번부터 세고, 같은 값이 여러 번 나오면 나온 횟수만큼 따로 센다. 정렬이 느린 홍준이를 대신해 $K$ 번째 값을 구하는 프로그램을 작성하라.

입력

첫째 줄에 $N$ 과 $K$ 가 공백을 사이에 두고 주어진다. ( $1 \le N \le 30000$ , $1 \le K \le N^2$ )

둘째 줄에 수열 $A$ 의 원소 $N$ 개가 공백을 사이에 두고 주어진다.

셋째 줄에 수열 $B$ 의 원소 $N$ 개가 공백을 사이에 두고 주어진다.

두 수열의 원소는 모두 $1$ 이상 $10^9$ 이하의 자연수이다.

출력

첫째 줄에 정렬한 원소 중 $K$ 번째로 작은 값을 출력한다.

예제2

예제 1
입력
```
2 3
2 3
3 5
```
예상 출력
```
10
```
예제 2
입력
```
3 5
2 2 2
3 3 3
```
예상 출력
```
6
```