안전 점검
시간 제한2초메모리 제한1024 MB
직선 도로 위 좌표 0에서 출발한 K명의 목수가 각 시설 i의 검사 항목 Bi개를 모두 검사해야 하며, 1분에 한 칸 이동하거나 항목 하나를 검사할 수 있을 때 검사를 끝내는 최소 시간을 구한다.
문제
JOI 시에는 충분히 긴 도로가 1개 있다. 이 도로는 수직선으로 볼 수 있고, 각 지점은 하나의 실수 좌표로 나타낸다. JOI 시에는 이 도로를 따라 N개의 시설이 있으며, 좌표가 작은 순서대로 1부터 N까지 번호가 붙어 있다. 시설 i (1 ≤ i ≤ N)의 위치는 좌표 Ai이다.
JOI 시에서는 이제 시설의 안전 점검을 실시한다. 시설 i에는 점검해야 할 항목이 Bi개 있다. 지금, 점검을 할 수 있는 K명의 목수가 모였다. 안전 점검이 시작될 때, 목수는 모두 좌표 0에 있다. 점검이 시작되면, 각 목수는 1분 동안 다음 2가지 행동 중 하나를 할 수 있다.
- 거리 1만큼 좌표를 이동한다.
- 현재 있는 좌표에 있는 시설의 점검 항목 중 1개를 골라 점검한다.
안전 점검을 마칠 때, 모든 건물의 모든 점검 항목이 1명 이상의 목수에 의해 점검되어 있어야 한다.
목수의 수와 시설 정보가 주어지므로, 안전 점검을 마치는 데 최소 몇 분이 걸리는지 구하는 프로그램을 작성하시오.
입력
입력은 다음 형식으로 표준 입력에서 주어진다.
N K
A1 A2 … AN
B1 B2 … BN
출력
표준 출력에, 안전 점검을 마치는 데 최소 몇 분이 걸리는지 1행으로 출력하시오.
제한
1 ≤ N ≤ 100 000.1 ≤ K ≤ 109.1 ≤ Ai ≤ 109(1 ≤ i ≤ N).Ai < Ai+1(1 ≤ i ≤ N-1).1 ≤ Bi ≤ 109(1 ≤ i ≤ N).- 입력되는 값은 모두 정수이다.