시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 28 15 10 43.478%

문제

홍준이에게는 길이가 N인 수열 2개 A와 B가 있습니다. 이 때 N2 크기의 행렬을 만드는데, 행렬의 i행 j열의 원소는 수열 A의 i번째 원소와 수열 B의 j번째 원소의 곱으로 정의합니다. 홍준이는 이 원소들을 모두 정렬하였습니다.

홍준이는 정렬된 결과에서 K번째(1번부터 계산)에 위치하는 값이 궁금해졌습니다. 하지만 계산이 느린 홍준이는 정렬하는데 너무 시간이 오래 걸리기 때문에 여러분에게 도움을 요청하였습니다. 홍준이를 도와 K번째 원소의 값을 구하는 프로그램을 작성하세요.

입력

첫째 줄에 N과 K가 주어집니다.(1≤N≤30000, 1≤K≤N2)

둘째 줄에 수열 A의 원소를 나타내는 N개의 정수가 공백을 사이에 두고 주어집니다.

셋째 줄에 수열 B의 원소를 나타내는 N개의 정수가 공백을 사이에 두고 주어집니다.

각 수열의 원소들은 1 이상 10억 이하의 자연수입니다.

출력

N2 크기의 행렬에서 K번째로 작은 수의 값을 출력합니다.

예제 입력 1

2 3
2 3
3 5

예제 출력 1

10