[고등부] 2022 KOI 1차대회 대비 모의고사 (4월 3주차)

재민이는 KOI 고등학교의 학생이다.

재민이는 이번 학기, 일주일에 N과목의 수업이 한 번씩 있으며 총 M주 동안 매주 모든 과목이 빠짐없이 수업을 한다.

이번 학기 재민이의 시험 전략은 낙제점을 피하기 위해, 모든 과목 중 최소 점수를 최대화하는 것이다.

재민이는 이를 위해서 수업을 듣는 대신 자습을 할 계획을 세웠다.

앞으로 다가올 총 NM번의 매 수업 시간마다 재민이는 두 가지 중 하나를 선택해 그 수업 내내 실행한다.

- 그 수업 시간의 수업 과목을 얌전히 앉아서 듣는다. 이 경우 그 과목을 i라고 하면 i에 대한 재민이의 시험점수가 A_i만큼 올라갈 것이다.

- 수업을 듣지 않고 그 수업의 원래 과목과 상관없이 원하는 과목을 아무거나 골라서 공부한다.
선택한 과목이 i라고 한다면 i 과목의 시험 성적이 B_i만큼 올라갈 것이다.

재민이가 수업을 듣거나 공부를 하기 전 초기 상태는 모든 과목에 대해 0점을 받는 상태이다.

재민이가 전략을 잘 세울 때 얻을 수 있는 최소 점수의 최댓값은 얼마일까?

입력

입력이 다음과 같은 형식으로 주어진다.

N M

A_1\, A_2\ \cdots\, A_N

B_1\, B_2\ \cdots\, B_N

<제한>

출력

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

부분문제

자습
서브태스크

1초 512MB