問題文

座標平面上に N 個の点があります。i 個目の点は、座標 (x_i, y_i) に位置しており、その価値は c_i です。

あなたの仕事は、N 個の点からちょうど K 個の点を選ぶことです。その後、以下のように変数を定めます。

• X_{\max} \coloneqq 選んだ点の x 座標の最大値
• X_{\min} \coloneqq 選んだ点の x 座標の最小値
• Y_{\max} \coloneqq 選んだ点の y 座標の最大値
• Y_{\min} \coloneqq 選んだ点の y 座標の最小値
• S \coloneqq 選んだ点の価値の総和

点を選び終えた後、あなたは報酬として (X_{\max} - X_{\min}) + (Y_{\max} - Y_{\min}) + S 円を獲得することができます。最大で何円の報酬を獲得可能か求めてください。

制約

• 入力は全て整数
• 1 \le K \le N \le 2 \times 10^5
• 1 \le x_i, y_i \le 10^9
• 1 \le c_i \le 10^9

部分点

• 1 \le N \le 1000 を満たすデータセットに正解した場合は 30 点が与えられる。

入力例1

3 2
1 3 1
3 1 1
3 3 2

出力例1

6

1 個目の点と 2 個目の点を選ぶと、報酬の額は (3 - 1) + (3 - 1) + 2 = 6 で、 6 円となります。これよりも高い額は達成不可能なので、6 が答えです。

入力例2

12 5
79 29 4
47 96 11
31 100 13
89 67 13
28 45 9
66 70 12
18 12 9
21 57 14
67 17 6
91 12 9
79 11 8
67 50 6

出力例2

220