配点: 100 点
JOI高中一年级 3 本学期是 1 每周 M 最多一周 M 一周 N 将举办该主题的课程。每个科目都有 它们的编号最大为 1 到 N 。另外,每周都有课程 N 有框架,每周 i 框架 (1 \leqq i \leqq N) 是主题 将举行 i 课程。
Bitaro 是一名高中一年级学生。 对于每个N \times M 块,您可以执行以下操作之一。
- 行動 1:参加该帧的课程。主题 i (1 \leqq i \leqq N) 类 1 如果你每堂课都参加,你对学科的理解就会降低。 A_i 增加。
- 行動 2:不参加该帧的课程并自由选择主题。 1 选择一个并自行研究。主题 i (1 \leqq i \leqq N)自学 1 如果您浏览一个框架,您对该主题的理解程度将为 B_i 增加。
然而,一开始,对各科目的理解程度较低。 0 。另外,由于我想在放学后花时间练习竞技性编程,所以我不会在课外时间学习。
3 本学期所有课程结束后,将举行期末考试。 Bitaro不想在考试中得红分,所以他想在考试时尽可能多地增加自己对理解水平最低的科目的理解。
给定学期的长度、科目的数量以及理解水平的提高,编写一个程序来找到考试时最大可能的最低理解水平。
入力
输入是按以下格式从标准输入给出的。所有输入值都是整数。
N M A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N
出力
标准输出包含进行测试时最大可能的最低理解水平。 1 行。
制約
- 1 \leqq N \leqq 300\,000.
- 1 \leqq M \leqq 1\,000\,000\,000.
- 1 \leqq A_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
- 1 \leqq B_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
小課題
- (10 点) M = 1.
- (25 点) N \times M \leqq 300\,000,A_i = B_i (1 \leqq i \leqq N).
- (27 点) N \times M \leqq 300\,000.
- (29 点) A_i = B_i (1 \leqq i \leqq N).
- (9 点)没有额外的限制。
入力例 1
3 3 19 4 5 2 6 2
出力例 1
18
例如,如果您按照以下方式学习,到考试时,您将能够 1, 2, 3 的理解程度是 19, 18, 19 变为。 本周
- 第 1 本周 1 框架是主题 自学 2 。 在
- 第 1 本周 2 框架是主题 自学 2 。 在
- 第 1 本周 3 框架是主题 自学 3 上课。
- 第 2 本周 1 框架是主题 自学 1 上课。
- 第 2 本周 2 框架是主题 自学 3 。 在
- 第 2 本周 3 框架是主题 自学 3 上课。
- 第 3 本周 1 框架是主题 自学 3 。 在
- 第 3 本周 2 框架是主题 自学 2 。 在
- 第 3 本周 3 框架是主题 自学 3 上课。
最低理解水平 19 没有办法做更多的事情,所以18 。
这个输入/输出示例是一个小任务。 3, 5 满足约束。
入力例 2
2 1 9 7 2 6
出力例 2
7
这个输入/输出示例是一个小任务。 1, 3, 5 满足约束。
入力例 3
5 60000 630510219 369411957 874325200 990002527 567203997 438920902 634940661 593780254 315929832 420627496
出力例 3
41397427274960
这个输入/输出示例是一个小任务。 3, 5 满足约束。
入力例 4
4 25 1 2 3 4 1 2 3 4
出力例 4
48
这个输入/输出示例是一个小任务。 2, 3, 4, 5 满足约束。