题目描述

在 JOI 高中高一的第三个学期的 $M$ 个星期的时间内，有 $N$ 门课，编号为 $1 \sim N$。每个星期有 $N$ 个课时，第 $i$ 个课时上课程 $i$ 的一节课。

比太郎是一位高一学生。对于 $N \times M$ 个课时中的每一个，他会选择如下行动中的一个：

• 行动 1：比太郎去上课。如果他去上了课程 $i$ 的一节课，那么他对课程 $i$ 的理解程度会增加 $A_i$。
• 行动 2：比太郎不去上课。他转而选择任意一门课，并且自学选中的那门课。如果他选中了课程 $i$ 进行了时长为一课时的自学，那么他对课程 $i$ 的理解程度会增加 $B_i$。

一开始，对每门课的理解程度都为 $0$。由于比太郎想要在课后练习算法竞赛，他在非上课时间内不会学习。当第三个学期的所有课时结束后，期末考就会举行。

比太郎不想挂科。所以他想要最大化在期末考时对每门课的理解程度的最小值。

给定学期的长度，课程的数量，以及对理解程度的提升数值，请写一个程序计算在期末考时对每门课的理解程度的最小值的最大可能值。

输入格式

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

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

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

输出格式

输出一行，一个数，表示在期末考时对每门课的理解程度的最小值的最大可能值。

3 3
19 4 5
2 6 2

18

2 1
9 7
2 6

7

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

41397427274960

4 25
1 2 3 4
1 2 3 4

48

提示

【样例解释 #1】

举个例子，如果比太郎按如下方式学习，则他对课程 $1, 2, 3$ 的理解程度将分别为 $19, 18, 19$。

• 第一周课程 $1$ 的课：自学课程 $2$；
• 第一周课程 $2$ 的课：自学课程 $2$；
• 第一周课程 $3$ 的课：去上课程 $3$ 的课；
• 第二周课程 $1$ 的课：去上课程 $1$ 的课；
• 第二周课程 $2$ 的课：自学课程 $3$；
• 第二周课程 $3$ 的课：去上课程 $3$ 的课；
• 第三周课程 $1$ 的课：自学课程 $3$；
• 第三周课程 $2$ 的课：自学课程 $2$；
• 第三周课程 $3$ 的课：去上课程 $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$ 分）：无特殊限制。

---

译自 JOI 2022 Final T2「自習 / Self Study」