AT_utpc2021_e Bounding Box

[problemUrl]: https://atcoder.jp/contests/utpc2021/tasks/utpc2021_e 座標平面上に $ 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 $ 円を獲得することができます。最大で何円の報酬を獲得可能か求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ x_1 $ $ y_1 $ $ c_1 $ $ \vdots $ $ x_N $ $ y_N $ $ c_N $

答えを $ 1 $ 行に出力せよ。

### 制約 - 入力は全て整数 - $ 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 $ 点が与えられる。 ### Sample Explanation 1 $ 1 $ 個目の点と $ 2 $ 個目の点を選ぶと、報酬の額は $ (3\ -\ 1)\ +\ (3\ -\ 1)\ +\ 2\ =\ 6 $ で、 $ 6 $ 円となります。これよりも高い額は達成不可能なので、$ 6 $ が答えです。