Problem Description

In the city of JOI, there is a single, sufficiently long road. This road can be considered as a number line, and each location is represented by a coordinate, which is a real number. Along this road, there are $N$ facilities installed, numbered from 1 to $N$ in increasing order of their coordinates. The position of facility $i$ (where $1 \leq i \leq N$) is at coordinate $A_i$.

The city of JOI is about to conduct a safety inspection of these facilities. Facility $i$ has $B_i$ items that need to be inspected. Currently, $K$ carpenters have been gathered who can perform the inspections. At the start of the safety inspection, all carpenters are at coordinate $0$. Once the inspection begins, each carpenter can perform one of the following actions in one minute:

• Move a distance of 1 coordinate.
• Inspect one item of the facility at the current coordinate.

By the end of the safety inspection, all inspection items of all facilities must be inspected by at least one carpenter.

Given the number of carpenters and the information about the facilities, create a program to determine the minimum number of minutes required to complete the safety inspection.

Input Format

The input is provided from the standard input in the following format:

$ N $ $ K $ $ A_1 $ $ A_2 $ $\cdots$ $ A_N $ $ B_1 $ $ B_2 $ $\cdots$ $ B_N $

Output Format

Output to the standard output the minimum number of minutes required to complete the safety inspection in one line.

Sample Input and Output

Sample Input #1

3 3
1 3 4
4 2 4

Sample Output #1

7

Sample Input #2

6 1
1 4 5 6 11 15
12 5 9 8 10 4

Sample Output #2

63

Sample Input #3

6 2
1 4 5 6 11 15
12 5 9 8 10 4

Sample Output #3

35

Sample Input #4

6 5
1 4 5 6 11 15
12 5 9 8 10 4

Sample Output #4

19

Notes/Hints

Constraints

• $1 \leq N \leq 100,000$.
• $1 \leq K \leq 10^9$.
• $1 \leq A_i \leq 10^9$ (where $1 \leq i \leq N$).
• $ A_i < A_{i+1} $ (where $1 \leq i \leq N-1$).
• $1 \leq B_i \leq 10^9$ (where $1 \leq i \leq N$).
• All input values are integers.

Subtasks

1. (3 points) $ K = 1 $.
2. (15 points) $ K = 2 $.
3. (82 points) No additional constraints.

Sample Explanation 1

For example, the inspection can be completed in 7 minutes by following these actions. Let's number the 3 carpenters as carpenter 1, 2, and 3.
1. Carpenters 1, 2, and 3 move to coordinate 1.
2. Carpenters 1, 2, and 3 each inspect one item of facility 1.
3. Carpenters 1 and 2 move to coordinate 2, and carpenter 3 inspects one item of facility 1.
4. Carpenters 1 and 2 move to coordinate 3, and carpenter 3 moves to coordinate 2.
5. Carpenters 1 and 2 move to coordinate 4, and carpenter 3 moves to coordinate 3.
6. Carpenters 1 and 2 each inspect one item of facility 3, and carpenter 3 inspects one item of facility 2.
7. Carpenters 1 and 2 each inspect one item of facility 3, and carpenter 3 inspects one item of facility 2.
It is impossible to complete the inspection in less than 7 minutes, so output 7.

Sample Explanation 2

This input example satisfies the constraints of subtasks 1 and 3.

Sample Explanation 3

This input example satisfies the constraints of subtasks 2 and 3.

见题面 Input 部分

见题面 Output 部分