래퍼의 레코드 제작

한 래퍼가 자신의 앨범을 바이닐(레코드판) 특별판으로 제작하려고 합니다. 각 레코드판은 먼저 공장에서 압착(press)한 뒤, 반짝이 가공 업체에서 표면을 반짝이로 덮어야 비로소 완성됩니다.

래퍼는 정확히 $k$장의 레코드판을 만들기로 계약했습니다. 압착 공장과 반짝이 가공 업체는 각각 하루에 레코드판을 한 장씩만 처리할 수 있습니다. 모든 레코드판은 반드시 압착을 먼저 한 뒤에 반짝이 가공을 해야 하지만, 같은 레코드판을 하루 안에 두 공정 모두 처리하는 것은 가능합니다. 또한 압착만 끝난 레코드판은 추가 비용 없이 원하는 만큼 오래 보관할 수 있습니다.

앞으로 $n$일 동안 날마다의 압착 비용과 반짝이 가공 비용이 주어집니다. 어느 날에 압착하고 어느 날에 반짝이 가공할지 정하여 $k$장을 완성하는 총비용을 최소로 만드세요.

첫째 줄에 두 정수 $n$과 $k$가 주어집니다 ($1 \le k \le n \le 5 \times 10^5$).

둘째 줄에는 $10^9$ 이하의 양의 정수 $n$개가 주어집니다. $i$번째 값은 $i$일째의 압착 비용입니다.

셋째 줄에는 $10^9$ 이하의 양의 정수 $n$개가 주어집니다. $i$번째 값은 $i$일째의 반짝이 가공 비용입니다.

반짝이로 덮인 레코드판 $k$장을 만드는 최소 총비용을 정수 하나로 출력하세요.

샘플 입력에서 한 가지 최적 방법은 다음과 같습니다. 1일째에 첫 번째 판을 압착하고 같은 날 반짝이 가공까지 끝냅니다. 두 번째 판은 2일째에 압착하여 4일째에 반짝이 가공합니다. 세 번째 판은 3일째에 압착하여 5일째에 반짝이 가공합니다. 네 번째 판은 6일째에 압착하여 8일째에 반짝이 가공합니다. 이때 총비용은 32입니다.