22355번 - 말뚝

UCPC 농장에는 $N$개의 말뚝이 일렬로 박혀 있다. 이 말뚝들은 높이가 무작위로 박혀 있어서 아름다워 보이지 않는다. 따라서 여러분은 말뚝들의 높이를 조정하여 UCPC 농장을 아름다워 보이게 만들어야 한다.

각 말뚝은 왼쪽에서 오른쪽으로 $1$부터 $N$까지 번호가 매겨져 있고, $i$번 말뚝의 처음 높이는 $H_i$ cm이다. 또한, 각 말뚝의 재질은 서로 다르기 때문에 각 말뚝을 들어올리거나 박는 데 필요한 힘이 제각각이다. $i$번 말뚝을 $1$cm만큼 들어올리는 데 $A_i$만큼의 힘이, $1$cm만큼 박는 데 $B_i$만큼의 힘이 든다.

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

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

첫 번째 줄에는 말뚝의 개수 $N$, 만족해야 하는 UCPC 농장의 아름다움 $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)$

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

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