문제
JOI시에는 하나의 충분히 긴 도로가 있습니다. 이 도로는 직선으로 간주 될 수 있으며 각 지점은 하나의 실수로 좌표로 표시됩니다. 또한 JOI시에는이 도로를 따라 N 개의 시설이 설치되어 있으며, 좌표가 작은 순서로 1에서 N까지의 번호가 붙어있다. 시설 i (1≤i≤N)의 위치는 좌표 Ai입니다.
JOI시에서는 앞으로 시설의 안전 점검이 실시된다. 시설 i에는 점검해야 할 항목이 Bi개 있다. 이제 점검을 할 수 있는 K인의 목수가 모였다. 안전 점검이 시작되면 목수는 모두 좌표 0에 있습니다. 점검이 시작되면 각 목수는 1 분 안에 다음 두 가지 행동 중 하나를 취할 수 있습니다.
거리 1만큼 좌표를 이동합니다.
지금의 좌표에 있는 시설의 점검 항목 중 1개의 항목을 선택하여 점검한다.
안전 점검을 마치면 모든 건물의 모든 점검 항목이 하나 이상의 목수에 의해 점검 되어야 한다.
목수의 인원수와 시설의 정보가 주어지므로, 안전 점검을 완료하는데 최단으로 몇 분 걸리는 지를 요구하는 프로그램을 작성하라.
입력
입력은 다음 형식으로 표준 입력에서 제공됩니다.
N K
A_1 A_2 … A_N
B_1 B_2 … B_N
[제한]
1 ≤ N ≤ 100 000.
1 ≤ K ≤ 10^9.
1 ≤ A_i ≤ 10^9 (1 ≤ i ≤ N).
Ai <A_{i + 1} (1 ≤ i ≤ N-1).
1 ≤ B_i ≤ 10^9 (1 ≤ i ≤ N).
입력 된 모든 값은 정수입니다.
출력
표준 출력에 안전 점검을 완료하는 데 최단으로 몇 분 걸리는지를 한 줄로 출력하라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 3점 | |
| #2 | 15점 | |
| #3 | 82점 | 추가 제한 없음 |
예제1
33
134
424
7
예를 들어, 다음과 같이 행동하면 7 분 만에 점검을 마칠 수 있습니다. 단 3명의 목수에 번호를 붙여 각각 목수 1, 2, 3으로 나타낸다.
목수 1, 2, 3은 좌표 1로 이동합니다.
목수 1, 2, 3이 각각 시설 1의 점검을 1항목씩 실시한다.
목수 1, 2는 좌표 2로 이동하고, 목수 3은 시설 1의 검사를 1항목 실시한다.
목수 1과 2는 좌표 3으로 이동하고 목수 3은 좌표 2로 이동합니다.
목수 1과 2는 좌표 4로 이동하고 목수 3은 좌표 3으로 이동합니다.
목수 1, 2가 각각 시설 3의 점검을 1항목씩 실시하고, 목수 3이 시설 2의 점검을 1항목 실시한다.
목수 1, 2가 각각 시설 3의 점검을 1항목씩 실시하고, 목수 3이 시설 2의 점검을 1항목 실시한다.
어쨌든 7 분 이내에 검사를 마칠 수 없으므로 7을 출력합니다.
예제2
61
14561115
12598104
63
예제3
62
14561115
12598104
35
예제4
65
14561115
12598104
19