32628번 - 두 스택

문제

승형이와 원빈이는 배낭여행을 가기 위해 두 개의 배낭을 준비했다. 각 배낭에는 $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 10^5, 0 \leq K \leq 2N)$

두 번째 줄에 첫 번째 배낭의 물건들의 무게를 나타내는 $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)$

출력

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

제한

노트

이 문제는 입력 데이터의 용량이 커서, 시간 초과를 받지 않으려면 빠른 입출력 방법을 사용해야 할 수 있다.

• C++을 사용하고 있고 cin/cout을 사용하고자 한다면:
  • cin.tie(nullptr)와 ios::sync_with_stdio(false)를 main 함수 안의 맨 위에 적는다.
  • endl 대신 개행 문자(\n)를 사용한다.
  • 단, 이렇게 할 경우 scanf/printf/puts/getchar/putchar 등 C의 입출력 방식을 사용하면 안 된다.
• Java를 사용하고 있다면:
  • Scanner와 System.out.println 대신 BufferedReader와 BufferedWriter를 사용한다.
  • BufferedWriter.flush를 마지막에 한 번 수행한다.
• Python을 사용하고 있다면:
  • input 대신 sys.stdin.readline을 사용한다. 단, 이 함수는 맨 끝의 개행 문자까지 같이 입력받음에 유의한다.
  • 개행 문자를 제외한 문자열을 저장하고 싶을 경우 .rstrip()을 추가로 해 주는 것이 좋다.