32631번 - 두 덱

문제

승형이와 원빈이는 배낭여행을 가기 위해 두 개의 배낭을 준비했다. 각 배낭에는 $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)$

출력

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

제한

힌트