Problem Description

In the third semester of the first year at JOI High School, there are $N$ courses numbered from $1$ to $N$ over a period of $M$ weeks. Each week consists of $N$ class periods, with the $i$-th period dedicated to course $i$.

Hitaro is a first-year student. For each of the $N \times M$ class periods, he will choose one of the following actions:

• Action 1: Hitaro attends class. If he attends a class for course $i$, his understanding of course $i$ increases by $A_i$.
• Action 2: Hitaro does not attend class. Instead, he chooses any course to study on his own. If he chooses course $i$ for a one-period self-study, his understanding of course $i$ increases by $B_i$.

Initially, his understanding of each course is $0$. Since Hitaro wants to practice competitive programming after class, he will not study during non-class hours. At the end of the third semester, a final exam will be held.

Hitaro does not want to fail. Therefore, he aims to maximize the minimum understanding of all courses at the time of the final exam.

Given the length of the semester, the number of courses, and the values of understanding increase, write a program to calculate the maximum possible value of the minimum understanding of all courses at the final exam.

Input Format

The first line contains two positive integers $N$ and $M$.

The second line contains $N$ positive integers $A_1, A_2, \ldots, A_N$.

The third line contains $N$ positive integers $B_1, B_2, \ldots, B_N$.

Output Format

Output a single number, which is the maximum possible value of the minimum understanding of all courses at the final exam.

Sample Input and Output

Sample Input #1

3 3
19 4 5
2 6 2

Sample Output #1

18

Sample Input #2

2 1
9 7
2 6

Sample Output #2

7

Sample Input #3

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

Sample Output #3

41397427274960

Sample Input #4

4 25
1 2 3 4
1 2 3 4

Sample Output #4

48

Notes

[Sample Explanation #1]

For example, if Hitaro studies as follows, his understanding of courses $1, 2, 3$ will be $19, 18, 19$ respectively.

• Week 1, Course 1: Self-study course $2$;
• Week 1, Course 2: Self-study course $2$;
• Week 1, Course 3: Attend course $3$;
• Week 2, Course 1: Attend course $1$;
• Week 2, Course 2: Self-study course $3$;
• Week 2, Course 3: Attend course $3$;
• Week 3, Course 1: Self-study course $3$;
• Week 3, Course 2: Self-study course $2$;
• Week 3, Course 3: Attend course $3$.

Since the minimum understanding of all courses cannot be greater than or equal to $19$, the output is $18$.

This sample satisfies the constraints of Subtasks $3, 5$.

[Sample Explanation #2]

This sample satisfies the constraints of Subtasks $1, 3, 5$.

[Sample Explanation #3]

This sample satisfies the constraints of Subtasks $3, 5$.

[Sample Explanation #4]

This sample satisfies the constraints of Subtasks $2, 3, 4, 5$.

[Data Range]

This problem is group-tested.

For $100\%$ of the data, $1 \le N \le 3 \times 10^5$, $1 \le M \le 10^9$, $1 \le A_i, B_i \le 10^9$.

• Subtask $1$ ($10$ points): $M = 1$.
• Subtask $2$ ($25$ points): $N \cdot M \le 3 \times 10^5$, $A_i = B_i$.
• Subtask $3$ ($27$ points): $N \cdot M \le 3 \times 10^5$.
• Subtask $4$ ($29$ points): $A_i = B_i$.
• Subtask $5$ ($9$ points): No additional constraints.

Translated from JOI 2022 Final T2 "自習 / Self Study"

见题面 Input 部分

见题面 Output 部分