Problem Description

There are $ N $ points on a coordinate plane. The $ i $-th point is located at coordinates $ (x_i, y_i) $ and has a value of $ c_i $.

Your task is to select exactly $ K $ points from these $ N $ points. Then, define the following variables:

• $X_{\max}$ $\coloneqq$ the maximum $ x $ coordinate of the selected points
• $X_{\min}$ $\coloneqq$ the minimum $ x $ coordinate of the selected points
• $Y_{\max}$ $\coloneqq$ the maximum $ y $ coordinate of the selected points
• $Y_{\min}$ $\coloneqq$ the minimum $ y $ coordinate of the selected points
• $ S $ $\coloneqq$ the sum of the values of the selected points

After selecting the points, you can earn a reward of $(X_{\max} - X_{\min}) + (Y_{\max} - Y_{\min}) + S$ yen. Determine the maximum possible reward you can earn.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ x_1 $ $ y_1 $ $ c_1 $ $\vdots$ $ x_N $ $ y_N $ $ c_N $

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

3 2
1 3 1
3 1 1
3 3 2

Sample Output #1

6

Sample Input #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

Sample Output #2

220

Notes/Hints

Constraints

• All inputs are integers.
• $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$

Partial Points

• If you solve the dataset where $1 \le N \le 1000$ correctly, you will be awarded $ 30 $ points.

Sample Explanation 1

Selecting the 1st and 2nd points, the reward amount is $ (3 - 1) + (3 - 1) + 2 = 6 $, which is $ 6 $ yen. A higher amount cannot be achieved, so the answer is $ 6 $.

见题面 Input 部分

见题面 Output 部分