Description

Along one side of a straight road there are many buildings, each with some primary school students. However, there is no primary school on this road. Therefore, the ever-mischievous "Niu A" plans to choose points on the road to build primary schools (they may coincide with building locations or not), so that the total walking distance of all students is minimized. Since building just one school cannot satisfy his desire for chaos, he decides to build K schools.

Input Format

• The first line contains two integers $n$ and $k$, the number of buildings and the number of schools ($1 \le n, k \le 100$).
• The second line contains $n$ integers, the number of students in each building (each count is between $1$ and $100$ inclusive).
• The third line contains $n - 1$ integers, where the $i$-th number is the distance between building $i$ and building $i + 1$ ($1 \le i \le n - 1$, each distance is between $1$ and $100$ inclusive).

Output Format

Output the minimal total walking distance of all students.

3 2
24 18 31
10 8

144

Hint

Translated by ChatGPT 5