题目描述

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

Bitaro 作为一名 JOI 中学的高中生，自然需要去学习。

在 JOI 中学，有 $N$ 门不同的课程，一个学期一共有 $M$ 周，对于每一周，会上 $N$ 次课，每一门课程恰好一周上一次课。Bitaro 对于每一个课程都有一个熟练度，初始时都为 $0$。

对于一节课 Bitaro 可以选择如下选项中的一个：

• 去上课：如果他上的是第 $i$ 门课，那么他对于这节课的熟练度增加 $A_i$。
• 翘课：Bitaro 热爱学习，所以他会选一门课自学，如果他选了第 $i$ 门课，那么他对于这节课的熟练度增加 $B_i$。

为了去更多的学习课外知识，Bitaro 不会在课下学习这 $N$ 门课程，但是他又不想要让自己挂科，于是他找到了你，他想让自己对每一门课的熟练度的最小值最大。

输入格式

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

接下来一行 $N$ 个整数 $A_i$。

接下来一行 $N$ 个整数 $B_i$。

输出格式

仅输出一行一个整数表示你的答案。

样例 1

输入

3 3
19 4 5
2 6 2

输出

18

方案说明：

• 第一周课程 1 的课：翘课学课程 2；
• 第一周课程 2 的课：翘课学课程 2；
• 第一周课程 3 的课：去上课；
• 第二周课程 1 的课：去上课；
• 第二周课程 2 的课：翘课学课程 2；
• 第二周课程 3 的课：翘课学课程 3；
• 第三周课程 1 的课：翘课学课程 3；
• 第三周课程 2 的课：翘课学课程 2；
• 第三周课程 3 的课：去上课；

可以证明，这是最优的方案。

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

样例 2

输入

2 1
9 7
2 6

输出

7

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

样例 3

输入

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

输出

41397427274960

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

样例 4

输入

4 25
1 2 3 4
1 2 3 4

输出

48

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

数据范围

对于全部数据 $1 \leq N \leq 3 \times 10^5$，$1 \leq M, A_i, B_i \leq 10^9$。

子任务	特殊限制	分数
1	$M = 1$	10
2	$N \times M \leq 3 \times 10^5$，$A_i = B_i$	25
3	$N \times M \leq 3 \times 10^5$	27
4	$A_i = B_i$	29
5	无特殊限制	9