자습

JOI 고등학교 1학년 3학기에 $N$개의 과목이 있고, 학기는 1주차부터 $M$주차까지 $M$주 동안 진행된다. 과목에는 $1$부터 $N$까지 번호가 붙어 있다. 매주 $N$개의 수업이 있으며, 각 주의 $i$번째 수업은 과목 $i$의 수업이다.

비타로는 1학년 학생이다. $N \times M$개의 수업 각각에서 그는 다음 두 가지 행동 중 하나를 한다.

• 행동 1: 수업에 참여한다. 과목 $i$($1 ≤ i ≤ N$)의 수업에 참여하면 과목 $i$의 이해도가 $A_i$만큼 증가한다.
• 행동 2: 수업에 참여하지 않는다. 대신 아무 과목 하나를 골라 그 과목을 혼자 공부한다. 수업 시간 동안 과목 $i$($1 ≤ i ≤ N$)를 혼자 공부하면 과목 $i$의 이해도가 $B_i$만큼 증가한다.

처음에 모든 과목의 이해도는 $0$이다. 비타로는 방과 후에 경쟁 프로그래밍을 연습하고 싶어 하므로 수업 시간 외에는 공부하지 않는다. 3학기의 모든 수업이 끝나면 기말고사가 열린다.

비타로는 낙제하고 싶지 않다. 따라서 기말고사 시점에 과목별 이해도의 최솟값을 최대화하려고 한다.

학기의 길이, 과목 수, 이해도 증가량이 주어질 때, 기말고사 시점에 가능한 과목별 이해도의 최솟값의 최댓값을 계산하는 프로그램을 작성하라.

표준 입력에서 다음 데이터를 읽는다. 주어지는 값은 모두 정수이다.

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

표준 출력에 한 줄을 출력한다. 기말고사 시점에 가능한 과목별 이해도의 최솟값의 최댓값을 출력해야 한다.

• $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$).