题目描述

给定两个长度为 n 的数组 a 和 b，以及一个整数 k。

你可以从数组 a 中任选一个数，从数组 b 中任选一个数，将这两个数相加，得到一个新的数。

一共有 n × n 种选法，每种选法都会得到一个和。

现在需要确定一个整数 ans。

对于每一种选法得到的和：

• 如果这个和 大于等于 ans，则这种选法是合法的；
• 如果这个和 小于 ans，则这种选法是不合法的。

请找到一个最小的整数 ans，使得：

合法选法数量 $\times ans \ge k$

输入格式

第一行输入两个整数：

n k

表示数组长度和目标值。

第二行输入 n 个整数：

a1 a2 ... an

表示数组 a。

第三行输入 n 个整数：

b1 b2 ... bn

表示数组 b。

输出格式

输出一个整数，表示满足条件的最小 ans。

样例

输入

2 3
1 2
4 5

输出

1

样例解释

数组：

a = [1, 2]
b = [4, 5]

所有可能的选法得到的和：

1 + 4 = 5
1 + 5 = 6
2 + 4 = 6
2 + 5 = 7

当：

ans = 1

所有 4 种选法均合法：

4 × 1 = 4 >= 3

满足条件。

当：

ans = 0

虽然仍有 4 种合法选法：

4 × 0 = 0 < 3

不满足条件。

因此答案为：

1

数据范围

对于所有测试数据：

• 1 <= n <= 100000
• 1 <= k <= 10^9
• 1 <= a[i], b[i] <= 10^9