문제
재민이는 KOI 고등학교의 학생이다.
재민이는 이번 학기, 일주일에 N과목의 수업이 한 번씩 있으며 총 M주 동안 매주 모든 과목이 빠짐없이 수업을 한다.
이번 학기 재민이의 시험 전략은 낙제점을 피하기 위해, 모든 과목 중 최소 점수를 최대화하는 것이다.
재민이는 이를 위해서 수업을 듣는 대신 자습을 할 계획을 세웠다.
앞으로 다가올 총 NM번의 매 수업 시간마다 재민이는 두 가지 중 하나를 선택해 그 수업 내내 실행한다.
- 그 수업 시간의 수업 과목을 얌전히 앉아서 듣는다. 이 경우 그 과목을 i라고 하면 i에 대한 재민이의 시험점수가 A_i만큼 올라갈 것이다.
- 수업을 듣지 않고 그 수업의 원래 과목과 상관없이 원하는 과목을 아무거나 골라서 공부한다. 선택한 과목이 i라고 한다면 i 과목의 시험 성적이 B_i만큼 올라갈 것이다.
재민이가 수업을 듣거나 공부를 하기 전 초기 상태는 모든 과목에 대해 0점을 받는 상태이다.
재민이가 전략을 잘 세울 때 얻을 수 있는 최소 점수의 최댓값은 얼마일까?
입력
입력이 다음과 같은 형식으로 주어진다.
N M
A_1 A_2 ... A_N
B_1 B_2 ... B_N
<제한>
- 1 <= N <= 300 000
- 1 <= M <= 1 000 000 000
- 1 <= A_i <= 1 000 000 000
- 1 <= B_i <= 1 000 000 000
<서브태스크>
#1 (10점) : M = 1
#2 (25점) : NM <= 300000, A_i=B_i
#3 (27점) : NM <= 300000
#4 (29점) : A_i = B_i
#5 (9점) : 추가적인 제한 조건이 없다.
출력
예제1
3 3
19 4 5
2 6 2
18
예제2
2 1
9 7
2 6
7
예제3
5 60000
630510219 369411957 874325200 990002527 567203997
438920902 634940661 593780254 315929832 420627496
41397427274960
예제4
4 25
1 2 3 4
1 2 3 4
48