問題文

JOI 市には 1 本の十分に長い道路がある．この道路は数直線とみなすことができ，各地点は 1 個の実数による座標で表される．また JOI 市にはこの道路に沿って N 個の施設が設置されており，座標の小さい順に 1 から N までの番号がつけられている．施設 i (1 \leqq i \leqq N) の位置は座標 A_i である．

JOI 市ではこれから施設の安全点検が行われる．施設 i には点検しなければならない項目が B_i 個ある．今，点検を行うことができる K 人の大工が集められた．安全点検の開始のとき，大工は全員が座標 0 にいる．点検が始まると，各大工は 1 分間で，次の 2 つの行動のどちらかをとることができる．

• 距離 1 だけ座標を移動する．
• 今いる座標にある施設の点検項目のうち，1 個の項目を選んで点検する．

安全点検を終えるとき，すべての建物のすべての点検項目が，1 人以上の大工によって点検されていなければならない．

大工の人数と施設の情報が与えられるので，安全点検を終えるのに最短で何分かかるかを求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 100\,000．
• 1 \leqq K \leqq 10^{9}．
• 1 \leqq A_i \leqq 10^{9} (1 \leqq i \leqq N)．
• A_i < A_{i+1} (1 \leqq i \leqq N-1)．
• 1 \leqq B_i \leqq 10^{9} (1 \leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (3 点) K = 1．
2. (15 点) K = 2．
3. (82 点) 追加の制約はない．

入力例 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