두 스택

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

둘째 줄에 첫 번째 배낭 물건들의 무게 $A_1, A_2, \dots, A_N$이 주어진다. $(1 \leq A_i \leq 10^9)$

셋째 줄에 두 번째 배낭 물건들의 무게 $B_1, B_2, \dots, B_N$이 주어진다. $(1 \leq B_i \leq 10^9)$

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

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

• C++에서 cin과 cout을 쓰려면:

  • main 함수 맨 위에 cin.tie(nullptr)와 ios::sync_with_stdio(false)를 적는다.
  • endl 대신 개행 문자(\n)를 쓴다.
  • 이 방식을 쓰면 scanf, printf, puts, getchar, putchar 같은 C의 입출력 함수를 쓰면 안 된다.

• Java를 쓴다면:

  • Scanner와 System.out.println 대신 BufferedReader와 BufferedWriter를 쓴다.
  • 마지막에 BufferedWriter.flush를 한 번 호출한다.

• Python을 쓴다면:

  • input 대신 sys.stdin.readline을 쓴다. 이 함수는 맨 끝의 개행 문자까지 함께 입력받는다.
  • 개행 문자를 뺀 문자열을 저장하고 싶다면 .rstrip()을 붙이는 것이 좋다.