레이팅 미적용JOI 市には 1 本の十分に長い道路がある.この道路は数直線とみなすことができ,各地点は 1 個の実数による座標で表される.また JOI 市にはこの道路に沿って N 個の施設が設置されており,座標の小さい順に 1 から N までの番号がつけられている.施設 i ( 1 ≦ i ≦ N ) の位置は座標 A i である.
JOI 市ではこれから施設の安全点検が行われる.施設 i には点検しなければならない項目が B i 個ある.今,点検を行うことができる K 人の大工が集められた.安全点検の開始のとき,大工は全員が座標 0 にいる.点検が始まると,各大工は 1 分間で,次の 2 つの行動のどちらかをとることができる.
距離 1 だけ座標を移動する.
今いる座標にある施設の点検項目のうち, 1 個の項目を選んで点検する.
安全点検を終えるとき,すべての建物のすべての点検項目が, 1 人以上の大工によって点検されていなければならない.
大工の人数と施設の情報が与えられるので,安全点検を終えるのに最短で何分かかるかを求めるプログラムを作成せよ.
1 ≦ N ≦ 100 000 .
1 ≦ K ≦ 10 9 .
1 ≦ A i ≦ 10 9 ( 1 ≦ i ≦ N ).
A i < A i+1 ( 1 ≦ i ≦ N-1 ).
1 ≦ B i ≦ 10 9 ( 1 ≦ i ≦ N ).
入力される値はすべて整数である.
( 3 点) K = 1 .
( 15 点) K = 2 .
( 82 点) 追加の制約はない.
入力は以下の形式で標準入力から与えられる.
N K
A 1 A 2 ... A N
B 1 B 2 ... B N
標準出力に,安全点検を終えるのに最短で何分かかるかを 1 行で出力せよ.
3 3
1 3 4
4 2 4
7
6 1
1 4 5 6 11 15
12 5 9 8 10 4
63
6 2
1 4 5 6 11 15
12 5 9 8 10 4
35
6 5
1 4 5 6 11 15
12 5 9 8 10 4
19