There are $N$ defensive towers on a map. The $i$-th tower is located at $(x_i, y_i)$ and has a value $c_i$. Stealing one tower takes one second.

Your teammate can distract the supervisor for $K$ seconds, so you can only steal $K$ towers.

Let:

• $X_{max}$ be the maximum $x$-coordinate among the $K$ towers you steal.
• $X_{min}$ be the minimum $x$-coordinate among the $K$ towers you steal.
• $Y_{max}$ be the maximum $y$-coordinate among the $K$ towers you steal.
• $Y_{min}$ be the minimum $y$-coordinate among the $K$ towers you steal.
• $S$ be the sum of the values $c$ of the $K$ towers you steal.

You need to choose $K$ towers to maximize $(X_{max}-X_{min})+(Y_{max}-Y_{min})+S$.

Input

The first line contains two integers $N$ and $K$.

The next $N$ lines each contain three integers $x_i, y_i, c_i$, representing the information of the $i$-th tower.

Output

Output a single integer representing the answer.

Examples

Input 1

3 2
1 3 1
3 1 1
3 3 2

Output 1

6

Note 1

Choose towers 1 and 2.

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

Output 2

220

Input 3

(See provided files)

Output 3

(See provided files)

Constraints

For all data, we have:

• $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$

Subtasks