| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 477 | 190 | 145 | 43.939% |
UCPC 농장에는 $N$개의 말뚝이 일렬로 박혀 있다. 이 말뚝들은 높이가 무작위로 박혀 있어서 아름다워 보이지 않는다. 따라서 여러분은 말뚝들의 높이를 조정하여 UCPC 농장을 아름다워 보이게 만들어야 한다.
각 말뚝은 왼쪽에서 오른쪽으로 1ドル$부터 $N$까지 번호가 매겨져 있고, $i$번 말뚝의 처음 높이는 $H_i$ cm이다. 또한, 각 말뚝의 재질은 서로 다르기 때문에 각 말뚝을 들어올리거나 박는 데 필요한 힘이 제각각이다. $i$번 말뚝을 1ドル$cm만큼 들어올리는 데 $A_i$만큼의 힘이, 1ドル$cm만큼 박는 데 $B_i$만큼의 힘이 든다.
UCPC 농장의 아름다움은 서로 높이가 같은 말뚝들로 이루어진 가장 긴 연속 구간의 길이로 결정된다. UCPC 농장의 아름다움을 $K$ 이상으로 만들기 위해 필요한 힘의 최솟값을 구해보자.
첫 번째 줄에는 말뚝의 개수 $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$ 이상으로 만들기 위해 필요한 힘의 최솟값을 출력한다.
2 2 1 3 4 1 1 3
6
5 3 1 2 3 2 1 1 3 1 3 4 1 3 5 3 1
5