두 덱

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각각 N개씩 쌓인 두 더미에서 위나 아래쪽 물건을 합쳐 최대 K번 제거한 뒤, 두 더미 중 무거운 쪽의 무게가 최소가 되도록 만드는 값을 구한다.

난이도: 보통10점 중 7점
유형: 배열, 누적 합, 완전 탐색, 그리디
정답자: 아직 제출이 없습니다

문제

승형이와 원빈이는 배낭여행을 가기 위해 두 개의 배낭을 준비했다. 각 배낭에는 $N$ 개의 물건이 들어있으며

첫 번째 배낭에는 $A\_1, A\_2, \dots, A\_N$ 의 무게를 가진 물건들이 아래에서 위로 순서대로 쌓여 있다. $A\_N$ 이 맨 위에 있는 물건의 무게이다.
두 번째 배낭에는 $B\_1, B\_2, \dots, B\_N$ 의 무게를 가진 물건들이 아래에서 위로 순서대로 쌓여 있다. $B\_N$ 이 맨 위에 있는 물건의 무게이다.

배낭의 무게는 배낭 안에 남아있는 물건들의 무게의 합으로 정의된다. 원빈이는 최대 $K$ 번 두 배낭 중 하나를 선택하여 맨 위 혹은 맨 아래에 있는 물건을 없앨 수 있다. 물건을 없애면 선택한 배낭의 무게는 없앤 물건의 무게만큼 줄어든다.

원빈이의 행동이 모두 끝난 후, 승형이는 자신이 멜 가방을 결정한다. 승형이는 약삭빠르기 때문에 항상 두 배낭 중 더 가벼운 배낭을 메고 다닌다. 만약 두 배낭의 무게가 같다면 둘 중 아무 배낭이나 메고 다닌다. 원빈이가 들어야 하는 배낭은 승형이가 선택하지 않은 배낭이다.

원빈이가 들어야 하는 배낭의 무게의 최솟값을 구해보자.

입력

첫 번째 줄에 두 정수 $N$ 과 $K$ 가 주어진다. $(1 \leq N \leq 5\\,000, 0 \leq K \leq N)$

두 번째 줄에 첫 번째 배낭의 물건들의 무게를 나타내는 $N$ 개의 정수 $A\_1, A\_2, \dots, A\_N$ 이 주어진다. $(1 \leq A\_i \leq 10^9)$

세 번째 줄에 두 번째 배낭의 물건들의 무게를 나타내는 $N$ 개의 정수 $B\_1, B\_2, \dots, B\_N$ 이 주어진다. $(1 \leq B\_i \leq 10^9)$

출력

원빈이가 들어야 하는 배낭의 무게의 최솟값을 출력한다.

예제2

예제 1
입력
```
3 2
3 1 4
1 5 9
```
예상 출력
```
6
```
예제 2
입력
```
3 0
3 1 4
1 5 9
```
예상 출력
```
15
```