안전 점검

문제

JOI 시에는 $1$ 개의 충분히 긴 도로가 있다. 이 도로는 수직선으로 볼 수 있으며, 각 지점은 $1$ 개의 실수 좌표로 표현된다. 또한 JOI 시에는 이 도로를 따라 $N$ 개의 시설이 설치되어 있으며, 좌표가 작은 순서대로 $1$ 부터 $N$ 까지의 번호가 붙어 있다. 시설 $i$ ($1 \le i \le N$) 의 위치는 좌표 $A_{i}$ 이다.

JOI 시에서는 이제부터 시설의 안전 점검이 이루어진다. 시설 $i$ 에는 점검해야 하는 항목이 $B_{i}$ 개 있다. 지금 점검을 할 수 있는 $K$ 명의 작업자가 모였다. 안전 점검을 시작할 때 작업자는 전원이 좌표 $0$ 에 있다. 점검이 시작되면 각 작업자는 $1$ 분 동안 다음 $2$ 가지 행동 중 하나를 할 수 있다.

• 거리 $1$ 만큼 좌표를 이동한다.
• 지금 있는 좌표에 있는 시설의 점검 항목 중에서 $1$ 개의 항목을 골라 점검한다.

안전 점검을 마칠 때, 모든 건물의 모든 점검 항목이 $1$ 명 이상의 작업자에 의해 점검되어 있어야 한다.

작업자의 수와 시설의 정보가 주어지므로, 안전 점검을 마치는 데 최소 몇 분이 걸리는지를 구하는 프로그램을 작성하시오.

제한

• $1 \le N \le 100\,000$.
• $1 \le K \le 10^{9}$.
• $1 \le A_{i} \le 10^{9}$ ($1 \le i \le N$).
• $A_{i} < A_{i+1}$ ($1 \le i \le N-1$).
• $1 \le B_{i} \le 10^{9}$ ($1 \le i \le N$).
• 입력되는 값은 모두 정수이다.

서브태스크

1. ($3$ 점) $K = 1$.
2. ($15$ 점) $K = 2$.
3. ($82$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 표준 입력에서 주어진다.
$N$ $K$
$A_{1}$ $A_{2}$ $\dots$ $A_{N}$
$B_{1}$ $B_{2}$ $\dots$ $B_{N}$

출력

표준 출력에 안전 점검을 마치는 데 최소 몇 분이 걸리는지를 $1$ 줄로 출력한다.

예제 입력 1

3 3
1 3 4
4 2 4

예제 출력 1

7

예를 들어 다음과 같이 행동함으로써 $7$ 분 만에 점검을 마칠 수 있다. 단, $3$ 명의 작업자에게 번호를 붙여 각각 작업자 $1,2,3$ 이라고 나타낸다.

1. 작업자 $1,2,3$ 이 좌표 $1$ 로 이동한다.
2. 작업자 $1,2,3$ 이 각각 시설 $1$ 의 점검을 $1$ 항목씩 수행한다.
3. 작업자 $1,2$ 가 좌표 $2$ 로 이동하고, 작업자 $3$ 이 시설 $1$ 의 점검을 $1$ 항목 수행한다.
4. 작업자 $1,2$ 가 좌표 $3$ 으로 이동하고, 작업자 $3$ 이 좌표 $2$ 로 이동한다.
5. 작업자 $1,2$ 가 좌표 $4$ 로 이동하고, 작업자 $3$ 이 좌표 $3$ 으로 이동한다.
6. 작업자 $1,2$ 가 각각 시설 $3$ 의 점검을 $1$ 항목씩 수행하고, 작업자 $3$ 이 시설 $2$ 의 점검을 $1$ 항목 수행한다.
7. 작업자 $1,2$ 가 각각 시설 $3$ 의 점검을 $1$ 항목씩 수행하고, 작업자 $3$ 이 시설 $2$ 의 점검을 $1$ 항목 수행한다.

어떻게 행동하더라도 $7$ 분 미만으로 점검을 마칠 수는 없으므로 $7$ 을 출력한다.

예제 입력 2

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

예제 출력 2

63

이 예제는 서브태스크 $1,3$ 의 제약을 만족한다.

예제 입력 3

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

예제 출력 3

35

이 예제는 서브태스크 $2,3$ 의 제약을 만족한다.

예제 입력 4

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

예제 출력 4

19