T834293 研习计划（study）

题目描述

研习班开设了 $N$ 门课程，编号为 $1$ 至 $N$，学习计划持续 $M$ 周。每周的课表都相同：按照课程 $1,2,\ldots,N$ 的顺序，每门课程各安排一节课。因此，整个学习计划共有 $NM$ 节课。

开始时，你对每门课程的熟练度都是 $0$。在课程 $i$ 的一节课中，你必须从以下两种方式中选择一种：

• 听这节课，使课程 $i$ 的熟练度增加 $A_i$；
• 自习一门自己选择的课程 $j$，使课程 $j$ 的熟练度增加 $B_j$。你可以选择任意一门课程，也可以选择当前课表上的课程，即允许 $j=i$。

一次选择只会增加所选课程的熟练度，其他课程的熟练度不变。不同课时的选择可以不同。课外没有额外的学习时间，熟练度也不会自行减少。

你希望在全部 $M$ 周结束后，所有课程中最低的熟练度尽可能高。这个最低熟练度最高能够达到多少？

输入格式

第一行包含一个整数 $T$，表示数据组数。接下来依次给出每组数据。

每组数据的第一行包含两个整数 $N,M$，分别表示课程数和周数。

第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$，表示听课时各门课程的熟练度增量。

第三行包含 $N$ 个整数 $B_1,B_2,\ldots,B_N$，表示自习时各门课程的熟练度增量。

输出格式

对于每组数据，输出一行一个整数，表示全部课程中最低熟练度的最大可能值。

输入输出样例 #1

输入 #1

1
3 3
19 4 5
2 6 2

输出 #1

18

说明/提示

可以采用下面的学习计划。表格各列分别对应每周课表中的三节课。

最终，课程 $1$ 的熟练度为 $19$，课程 $2$ 的熟练度为 $6+6+6=18$，课程 $3$ 的熟练度为 $5+2+5+2+5=19$，最低熟练度为 $18$。

如果希望三门课程的熟练度都至少为 $19$，课程 $1$ 至少需要一节课，课程 $2$ 至少需要四节课；课程 $3$ 即使听满三节本课，也还需要两节自习，共至少五节课。这样至少需要 $1+4+5=10$ 节课，超过了实际的九节课，因此答案为 $18$。

样例 2

见 考生目录/study/study2.in 与 考生目录/study/study2.ans。该样例满足测试点 $1\sim2$ 的约束。

样例 3

见 考生目录/study/study3.in 与 考生目录/study/study3.ans。该样例满足测试点 $3\sim7$ 的约束。

样例 4

见 考生目录/study/study4.in 与 考生目录/study/study4.ans。该样例满足测试点 $8\sim12$ 的约束。

样例 5

见 考生目录/study/study5.in 与 考生目录/study/study5.ans。该样例满足测试点 $13\sim18$ 的约束。

样例 6

见 考生目录/study/study6.in 与 考生目录/study/study6.ans。该样例满足测试点 $19\sim20$ 的约束。

样例 7

见 考生目录/study/study7.in 与 考生目录/study/study7.ans。该样例满足测试点 $19\sim20$ 的约束。

数据范围

对于所有数据，保证：

• $1\le T\le10$；
• 每组数据中，$1\le N\le3\times10^5$；
• 每组数据中，$1\le M,A_i,B_i\le10^9$；
• 同一输入文件中，所有数据的 $N$ 之和不超过 $6\times10^5$。