在 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

2 1
9 7
2 6

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

41397427274960

4 25
1 2 3 4
1 2 3 4

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

EOJ-自适应编程学习平台

E. 自学