Fence Posts

Time limit5sMemory limit1024 MB

Summary

Given post heights and per-post costs to raise or lower them by 1 cm, find the minimum total cost so that some K consecutive posts end at the same height.

Level: Hard8 of 10
Topics: Prefix sum, Sliding window, Binary search, Sorting
Solved: No attempts yet

Problem

At the UCPC farm, $N$ fence posts are driven in a row. Their heights are random, so the farm does not look beautiful. You must adjust the heights of the posts to make the farm beautiful.

The posts are numbered $1$ through $N$ from left to right, and the initial height of post $i$ is $H_i$ cm. Each post is made of a different material, so lifting or driving each post takes a different amount of force. Lifting post $i$ by $1$ cm takes $A_i$ of force, and driving it in by $1$ cm takes $B_i$ of force.

The beauty of the UCPC farm is the length of the longest contiguous segment of posts that all have the same height. Find the minimum force needed to make the beauty of the farm at least $K$ .



Figure E.1: The initial state of the posts, with beauty 1	Figure E.2: Spending force to raise the beauty to 3

Input

The first line gives the number of posts $N$ and the required beauty of the farm $K$ . $(1 \leq N \leq 100\ 000, 1 \leq K \leq N)$

The next line gives the initial heights of the posts $H_1, H_2, \cdots, H_N$ , separated by spaces. $(1 \leq H_i \leq 100\ 000, 1 \leq i \leq N)$

The next line gives the force needed to lift each post by $1$ cm, $A_1, A_2, \cdots, A_N$ , separated by spaces. $(1 \leq A_i \leq 20\ 000, 1 \leq i \leq N)$

The next line gives the force needed to drive each post in by $1$ cm, $B_1, B_2, \cdots, B_N$ , separated by spaces. $(1 \leq B_i \leq 20\ 000, 1 \leq i \leq N)$

All values in the input are integers.

Output

On the first line, output the minimum force needed to make the beauty of the farm at least $K$ .

Examples2

Example 1
Input
```
2 2
1 3
4 1
1 3
```
Expected output
```
6
```
Example 2
Input
```
5 3
1 2 3 2 1
1 3 1 3 4
1 3 5 3 1
```
Expected output
```
5
```