注：P3 见 CodeForces-546E

题目描述

数组 A 和数组 B，里面都有 n 个整数。数组 C 共有 n ^ 2 个整数，分别是 A0 * B0, A0 * B1, …, A1 * B0, A1 * B1, …, An-1 * Bn-1（数组 A 同数组 B 的组合）。求数组 C 中第 K 大的数。

输入格式

第 1 行：2 个数 N 和 K，中间用空格分隔。N, K 意义如题目描述。
第 2 - N + 1 行：每行 2 个数，分别是 Ai 和 Bi。

输出格式

输出第 K 大的数。

样例输入

3 2
1 2
2 3
3 4

样例输出

9

数据范围

对于 30%的数据 2 <= N <= 50，1 <= K <= 2000，1 <= Ai, Bi <= 2000；
对于 100%的数据 2 <= N <= 50000，1 <= K <= 10 ^ 9，1 <= Ai, Bi <= 10 ^ 9。

限制

1s

样例解释

对于样例，A：1 2 3，B：2 3 4。A 与 B 组合成的 C 包括 2 3 4 4 6 8 6 9 12 共 9 个数，第二大的为 9。

来源

CWOI新高二专题测试十二