There are $N$ stakes driven in a row at the UCPC farm. These stakes are driven to random heights, so they do not look beautiful. Therefore, you need to adjust the heights of the stakes to make the UCPC farm look beautiful.

Each stake is numbered from $1$ to $N$ from left to right, and the initial height of the $i$-th stake is $H_i$ cm. Also, because the material of each stake is different, the force required to pull up or drive down each stake varies. It takes $A_i$ units of force to pull up the $i$-th stake by 1 cm, and $B_i$ units of force to drive down the $i$-th stake by 1 cm.

The beauty of the UCPC farm is determined by the length of the longest contiguous segment of stakes that have the same height. Let's find the minimum force required to make the beauty of the UCPC farm at least $K$.

Figure E.1: Initial state of stakes with beauty 1

Figure E.2: Increasing the beauty to 3 by applying force

Input

The first line contains the number of stakes $N$ and the required beauty $K$ of the UCPC farm. ($1 \le N \le 100\,000$, $1 \le K \le N$)

The next line contains the initial heights of each stake, $H_1, H_2, \dots, H_N$, separated by spaces. ($1 \le H_i \le 100\,000$, $1 \le i \le N$)

The next line contains the force required to pull up each stake by 1 cm, $A_1, A_2, \dots, A_N$, separated by spaces. ($1 \le A_i \le 20\,000$, $1 \le i \le N$)

The next line contains the force required to drive down each stake by 1 cm, $B_1, B_2, \dots, B_N$, separated by spaces. ($1 \le B_i \le 20\,000$, $1 \le i \le N$)

All values given in the input are integers.

Output

Print the minimum force required to make the beauty of the UCPC farm at least $K$ on the first line.

Examples

Input 1

2 2
1 3
4 1
1 3

Output 1

6

Input 2

5 3
1 2 3 2 1
1 3 1 3 4
1 3 5 3 1

Output 2

5