시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB257908042.553%

문제

이 문제는「낚시 (Hard)」문제의 쉬운 버전으로, 입력 조건, 변수 범위, 문제 상황 등은 동일하지만 정답으로 요구되는 출력 형식이 다릅니다.

”낚시란, 더 큰 것을 얻기 위해 작은 것을 바치는 것이다.”

— 그런 말 한 사람 없음

2025년의 모든 시험과 과제를 끝마친 당신은 마음의 평화를 찾기 위해 낚시터를 찾았다.

현재 낚시터에는 $M$마리의 물고기가 있으며, 당신은 $N$개의 떡밥을 가지고 있다. 각 물고기와 떡밥은 양의 정수 값의 가치를 가진다.

당신은 가지고 있는 떡밥을 활용하여 원하는 만큼 낚시를 할 수 있다. 이때 가지고 있는 떡밥들 중 하나 이상을 골라 낚싯대에 달고 낚시를 하면, 사용한 떡밥을 모두 잃는 대신 낚시터에 있는 물고기들 중 당신이 사용한 떡밥의 가치의 총합보다 큰 가치의 물고기가 잡힌다. 만약 이러한 물고기가 하나 이상이라면 이들 중 가장 낮은 가치의 물고기가 잡히게 되며, 사용한 떡밥의 가치의 총합보다 높은 가치의 물고기가 없다면 물고기가 잡히지 않는다. 잡은 물고기는 당신이 보유하게 된다.

이때, 가지고 온 $N$개의 떡밥 외에 낚시를 통해 얻은 물고기 한 마리를 소모하여 같은 가치의 떡밥 한 개를 만들 수 있다. 떡밥 만들기는 낚시를 진행하는 중이라면 아무 때나 원하는 만큼 진행할 수 있다.

당신은 낚시를 마친 후 보유한 물고기들의 가치의 합을 최대화하려고 한다. 슬기롭게 낚시를 진행하여 최고의 낚시꾼이 되어보자!

입력

첫째 줄에 보유한 떡밥의 수 $N$과 낚시터에 있는 물고기의 수 $M$이 공백으로 구분되어 주어진다.

둘째 줄에 보유한 떡밥 $N$개의 가치 $b_1$, $b_2$, $\cdots$, $b_N$이 공백으로 구분되어 주어진다.

셋째 줄에 낚시터에 있는 물고기 $M$마리의 가치가 $f_1$, $f_2$, $\cdots$, $f_M$이 공백으로 구분되어 주어진다.

출력

첫째 줄에 보유한 물고기들의 가치의 합의 최댓값을 출력한다.

제한

  • $1\leq N\leq 10^5$
  • $1\leq M\leq 10^5$
  • $1\leq b_i\leq 10^8$ $(1\leq i\leq N)$
  • $1\leq f_i\leq 10^8$ $(1\leq i\leq M)$

서브태스크

번호배점제한
116

임의의 $1\leq i\leq N$, $1\leq j\leq M$에 대해, $b_i<f_j$

219

임의의 $1<i\leq N$, $1<j\leq M$에 대해, $b_i=b_1+i-1$, $f_j=f_1+j-1$

365

추가 제한 조건이 없습니다.

예제 입력 1

5 3
2 2 6 7 8
8 10 11

예제 출력 1

29

예제 입력 2

2 3
1 9
5 10 11

예제 출력 2

21

출처

School > 서울과학고등학교 > SciOI 2025 B1번

채점 및 기타 정보

  • 예제는 채점하지 않는다.