Self Study

Time limit1sMemory limit512 MB

Summary

Given N courses over M weeks, each class Bitaro either attends (gaining A_i in course i) or self-studies one course (gaining B_i); maximize the minimum final comprehension across all courses.

Level: Hard8 of 10
Topics: Binary search, Greedy, Math, Implementation
Solved: No attempts yet

Problem

In the third semester of the first grade of JOI High School, $N$ courses are given over $M$ weeks, from the first week to the $M$ -th week. The courses are numbered from $1$ to $N$ . In each week, $N$ classes are given. The $i$ -th class in each week is a class for Course $i$ .

Bitaro is a student of the first grade. In each of the $N \times 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 level of Course $i$ will be increased by $A_i$ .
Action 2: Bitaro does not attend the class. Instead, he chooses any one of the courses, and studies for the chosen 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 $B_i$ .

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 third semester 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 of the courses at the moment of the final examination.

Input

Read the following data from the standard input. Given values are all integers.

$\begin{align*} & N\,M \\ & A_1 \, A_2 \, \cdots \, A_N \\ & B_1 \, B_2 \, \cdots \, B_N \end{align*}$

Output

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.

Constraints

$1 ≤ N ≤ 300\,000$ .
$1 ≤ M ≤ 1\,000\,000\,000$ .
$1 ≤ A_i ≤ 1\,000\,000\,000$ ( $1 ≤ i ≤ N$ ).
$1 ≤ B_i ≤ 1\,000\,000\,000$ ( $1 ≤ i ≤ N$ ).

Examples4

Example 1
Input
```
3 3
19 4 5
2 6 2
```
Expected output
```
18
```
Example 2
Input
```
2 1
9 7
2 6
```
Expected output
```
7
```

Example 3

Input

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

Expected output

41397427274960

Example 4
Input
```
4 25
1 2 3 4
1 2 3 4
```
Expected output
```
48
```