JOI 2022- 자습 > 문제은행 : 정보올림피아드&알고리즘



5043 : 자습

제한시간
1000 ms   
메모리제한
512 MB   
해결횟수
0 회   
시도횟수
0 회   

문제

재민이는 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점) : 추가적인 제한 조건이 없다.


출력형식

가능한 방법 중, 점수의 최소의 최대값을 한 줄로 출력하라.

입력 예

복사하기

3 3
19 4 5
2 6 2

출력 예

복사하기

18

입력 예

복사하기

2 1
9 7
2 6

출력 예

복사하기

7

입력 예

복사하기

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

출력 예

복사하기

41397427274960

입력 예

복사하기

4 25
1 2 3 4
1 2 3 4

출력 예

복사하기

48

출처

JOI 2022

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP