말뚝

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

요약

기둥의 높이와 기둥마다 1cm 올리거나 내리는 데 드는 힘이 주어질 때, 연속한 K개의 기둥을 같은 높이로 만드는 최소 힘을 구한다.

난이도: 어려움10점 중 8점
유형: 누적 합, 슬라이딩 윈도우, 이분 탐색, 정렬
정답자: 아직 제출이 없습니다

문제

UCPC 농장에는 $N$ 개의 말뚝이 일렬로 박혀 있다. 말뚝의 높이가 제각각이라 농장이 아름다워 보이지 않는다. 그래서 말뚝의 높이를 조정해 농장을 아름답게 만들어야 한다.

각 말뚝에는 왼쪽에서 오른쪽으로 $1$ 부터 $N$ 까지 번호가 붙어 있고, $i$ 번 말뚝의 처음 높이는 $H_i$ cm이다. 말뚝마다 재질이 달라서, 말뚝을 들어올리거나 박는 데 드는 힘도 각각 다르다. $i$ 번 말뚝을 $1$ cm 들어올리는 데 $A_i$ 만큼의 힘이 들고, $1$ cm 박는 데 $B_i$ 만큼의 힘이 든다.

UCPC 농장의 아름다움은 높이가 같은 말뚝들이 이루는 가장 긴 연속 구간의 길이로 정해진다. 농장의 아름다움을 $K$ 이상으로 만들기 위해 필요한 힘의 최솟값을 구하자.



그림 E.1: 아름다움이 1인 초기 말뚝의 상태	그림 E.2: 힘을 들여 아름다움을 3으로 늘리는 모습

입력

첫 번째 줄에는 말뚝의 개수 $N$ 과 만족해야 하는 농장의 아름다움 $K$ 가 주어진다. $(1 \leq N \leq 100\ 000, 1 \leq K \leq N)$

다음 줄에는 각 말뚝의 처음 높이 $H_1, H_2, \cdots, H_N$ 가 공백으로 구분되어 주어진다. $(1 \leq H_i \leq 100\ 000, 1 \leq i \leq N)$

다음 줄에는 각 말뚝을 $1$ cm 들어올리는 데 필요한 힘 $A_1, A_2, \cdots, A_N$ 가 공백으로 구분되어 주어진다. $(1 \leq A_i \leq 20\ 000, 1 \leq i \leq N)$

다음 줄에는 각 말뚝을 $1$ cm 박는 데 필요한 힘 $B_1, B_2, \cdots, B_N$ 가 공백으로 구분되어 주어진다. $(1 \leq B_i \leq 20\ 000, 1 \leq i \leq N)$

입력으로 주어지는 모든 값은 정수이다.

출력

첫째 줄에 농장의 아름다움을 $K$ 이상으로 만들기 위해 필요한 힘의 최솟값을 출력한다.

예제2

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