You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

魔法课

题目描述

魔法学徒小明快要期末考试了，他现在非常不安，因为他一直在摸鱼，啥也不会！

离期末考试还有 $N$ 周，魔法学院的期末考总共考 $M$ 门魔法课，每周每门魔法课恰好上一节。

小明在每节课的时间可以选择去听课，听第 $i$ 门魔法课可以让他对这门魔法的熟练度增加 $a_i$ ，或者可以不去听课而是去自学，自学第 $j$ 门魔法课可以让他对这门魔法的熟练度增加 $b_j$ 。注意：因为有些老师可能不太会教魔法（尽管他们可能很厉害），小明上某些课能增加的熟练度可能不如自学。

因为小明啥也不会，所以他初始对任何一门魔法课的熟练度都是 $0$ 。同时因为小明实在是太喜欢摸鱼了，他不会在上课时间以外的任何时间进行任何的魔法练习，但是他又不想挂科，所以他想知道，在期末考试的时候，他熟练度最小的那一门魔法的最大熟练度可以是多少。

输入格式

第一行，两个正整数 $N, M$。

第二行，$N$ 个正整数 $A_1, A_2, \ldots, A_N$。

第三行，$N$ 个正整数 $B_1, B_2, \ldots, B_N$。

输出格式

输出一行，一个数，表示熟练度最小的那一门魔法的最大熟练度。

样例 #1

样例输入 #1

3 3
19 4 5
2 6 2

样例输出 #1

18

样例 #2

样例输入 #2

2 1
9 7
2 6

样例输出 #2

7

样例 #3

样例输入 #3

5 60000
630510219 369411957 874325200 990002527 567203997
438920902 634940661 593780254 315929832 420627496

样例输出 #3

41397427274960

样例 #4

样例输入 #4

4 25
1 2 3 4
1 2 3 4

样例输出 #4

48

提示

【样例解释 #1】

举个例子，如果小明按如下方式学习，则他对魔法 $1, 2, 3$ 的熟练度将分别为 $19, 18, 19$。

• 第一周魔法 $1$ 的课：自学魔法 $2$；
• 第一周魔法 $2$ 的课：自学魔法 $2$；
• 第一周魔法 $3$ 的课：去上课；
• 第二周魔法 $1$ 的课：去上课；
• 第二周魔法 $2$ 的课：自学魔法 $3$；
• 第二周魔法 $3$ 的课：去上课；
• 第三周魔法 $1$ 的课：自学魔法 $3$；
• 第三周魔法 $2$ 的课：自学魔法 $2$；
• 第三周魔法 $3$ 的课：去上课。

由于对每门魔法的最小的理解程度不能大于等于 $19$，输出 $18$。

这个样例满足子任务 $3, 5$ 的限制。

【样例解释 #2】

这个样例满足子任务 $1, 3, 5$ 的限制。

【样例解释 #3】

这个样例满足子任务 $3, 5$ 的限制。

【样例解释 #4】

这个样例满足子任务 $2, 3, 4, 5$ 的限制。

【数据范围】

对于 $100 \%$ 的数据，$1 \le N \le 3 \times {10}^5$，$1 \le M \le {10}^9$，$1 \le A_i, B_i \le {10}^9$。

• 子任务 $1$（$10$ 分）：$M = 1$。
• 子任务 $2$（$25$ 分）：$N \cdot M \le 3 \times {10}^5$，$A_i = B_i$。
• 子任务 $3$（$27$ 分）：$N \cdot M \le 3 \times {10}^5$。
• 子任务 $4$（$29$ 分）：$A_i = B_i$。
• 子任务 $5$（$9$ 分）：无特殊限制。