The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Final RoundFebruary 13, 2022 (Online)

2Self StudyIn the third semester of the first grade of JOI High School, N courses are given for M weeks from the firstweek to the M-th week. The courses are numbered from 1 to N. In each week, N classes are given. The i-thclass in each week is a class for Course i.
Bitaro is a student of the first grade. In each of the N × M classes, he takes one of the following actions.
• Action 1: Bitaro attends the class. If he attends a class for Course i (1 ≤ i ≤ N), the comprehension levelof Course i will be increased by Ai .
• Action 2: Bitaro does not attend the class. Instead, he chooses any one of the courses, and studies for thechosen course by himself. If he studies for Course i (1 ≤ i ≤ N) by himself for the duration of a class,the comprehension level of Course i will be increased by Bi .
In the beginning, the comprehension level of every course is 0. Since Bitaro wants to practice competitive
programming after school, he will not study outside the duration of the classes. When all the classes in the thirdsemester finish, the final examination will be held.
Bitaro does not want to get a failing grade. Therefore, he wants to maximize the minimum comprehension
level of the courses at the moment of the final examination.
Given the length of the semester, the number of the courses, and the incremental values of the comprehension
levels, write a program which calculates the maximum possible value of the minimum comprehension level ofthe courses at the moment of the final examination.

Input
Read the following data from the standard input. Given values are all integers.
NMA1 A2 · · · AN
B1 B2 · · · BNOutput
Write one line to the standard output. The output should contain the maximum possible value of the minimum
comprehension level of the courses at the moment of the final examination.

Task 2- 1 / 3

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Final Round
February 13, 2022 (Online)

Constraints• 1 ≤ N ≤ 300 000.
• 1 ≤ M ≤ 1 000 000 000.
• 1 ≤ Ai ≤ 1 000 000 000 (1 ≤ i ≤ N).
• 1 ≤ Bi ≤ 1 000 000 000 (1 ≤ i ≤ N).

Subtasks
1. (10 points) M = 1.
2. (25 points) N × M ≤ 300 000，Ai = Bi (1 ≤ i ≤ N).
3. (27 points) N × M ≤ 300 000.
4. (29 points) Ai = Bi (1 ≤ i ≤ N).
5. (9 points) No additional constraints.

Sample Input and Output
Sample Input 1

Sample Output 1

3 318

19 4 52 6 2For example, if Bitaro studies in the following way, the compehension level of Course 1, 2, 3 will be 19, 18, 19,
respectively.
• In the first week, at the time of Course 1, he studies for Course 2 by himself.
• In the first week, at the time of Course 2, he studies for Course 2 by himself.
• In the first week, at the time of Course 3, he attends the class for Course 3.
• In the second week, at the time of Course 1, he attends the class for Course 1.
• In the second week, at the time of Course 2, he studies for Course 3 by himself.
• In the second week, at the time of Course 3, he attends the class for Course 3.
• In the third week, at the time of Course 1, he studies for Course 3 by himself.
• In the third week, at the time of Course 2, he studies for Course 2 by himself.
• In the third week, at the time of Course 3, he attends the class for Course 3.

Task 2- 2 / 3

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Final Round
February 13, 2022 (Online)

Since the minimum comprehension level of the courses cannot be larger than or equal to 19, output 18.
This sample input satisfies the constraints of Subtasks 3, 5.
Sample Input 2Sample Output 22 179 72 6This sample input satisfies the constraints of Subtasks 1, 3, 5.
Sample Input 3

Sample Output 35 60000

41397427274960

630510219 369411957 874325200 990002527 567203997
438920902 634940661 593780254 315929832 420627496
This sample input satisfies the constraints of Subtasks 3, 5.
Sample Input 4

Sample Output 44 2548

1 2 3 41 2 3 4This sample input satisfies the constraints of Subtasks 2, 3, 4, 5.

Task 2- 3 / 3