Maximizing Minimum Course Understanding

In a school term of M weeks, there are N subjects (numbered from 1 to N). In each week there are exactly N class periods: in the i-th period the scheduled lecture is for subject i.

Student Bitaro can take one of the following actions in every one of the total N × M periods:

• Action 1 (Attend class): If Bitaro attends the scheduled lecture for subject i, his understanding of that subject increases by A_i.
• Action 2 (Self‐study): If he skips the scheduled lecture, he may choose any subject i to study on his own for that period; doing so increases his understanding of subject i by B_i.

Initially, his understanding in every subject is 0. When all the periods in the term are finished, the final exam will be held. Bitaro wants to avoid failing any subject, so his goal is to maximize the minimum understanding level across all subjects at the final exam.

Given the number of subjects, the number of weeks, and the improvement values for each subject, compute the maximum possible minimum understanding level that Bitaro can achieve by the end of the term.

Note on scoring: If Bitaro allocates a periods to attending the scheduled lecture for a subject (with improvement A_i) and x periods to self‐study for that subject (with improvement B_i), his total improvement for that subject will be a × A_i + x × B_i. Moreover, the total number of periods used (for all subjects) must equal N × M.

inputFormat

The input consists of three lines:

1. The first line contains two integers N and M — the number of subjects and the number of weeks respectively.
2. The second line contains N integers A₁, A₂, ..., A_N — the increase in understanding if Bitaro attends the scheduled class for each subject.
3. The third line contains N integers B₁, B₂, ..., B_N — the increase in understanding if he self‐studies that subject for one period.

All numbers are positive integers.

outputFormat

Output one integer — the maximum possible value of the minimum understanding level among all subjects at the end of the term.

sample

3 2
3 1 2
1 2 1

4