题目背景

打地鼠是这样的一个游戏：地面上有一些地鼠洞，地鼠们会不时从洞里探出头来透气，很快时间后又缩回洞中。玩家的目标是在地鼠伸出头时，用锤子砸其头部，砸到的地鼠越多分数也就越高。

题目描述

游戏里一共会出现 $n$ 个地鼠，在 $t_i$ 时刻，第 $i$ 个地鼠出现了，它探出头的位置是 $(x_i,y_i)$，并且下一时刻会立即消失。

当游戏开始时，你可以消耗 1 金币操纵玩家移动，即玩家用时 1 秒 从坐标 $(i,j)$ 移向 $(i,j+1)$，$(i,j-1)$，$(i+1,j)$，$(i-1,j)$ 四个坐标之一。最初玩家在坐标 $(0,0)$。当某一时刻，玩家和地鼠在同一坐标的话，玩家就可以砸到这个地鼠。(落锤的时间和金币消耗忽略不计)。

现在想知道游戏中砸到 $k$ 只地鼠最少需要花费多少金币？ 如果无法完成任务，输出 -1 。

数据范围

对于 $30$%的数据： $1≤n≤20,1≤k≤n,1≤x_i,y_i≤100,1≤t_i≤10^4$。

对于 $100$%的数据： $1≤n≤100,1≤k≤n,1≤x_i,y_i≤1000,1≤t_1<t_2<t_3<...<t_n≤10^6$。

同一时刻最多出现一个地鼠。

输入格式

第一行包含两个正整数 $n,k$，表示游戏当中共出现的地鼠数量，以及需要砸到的地鼠数量。

接下来 $n$ 行，每行三个整数 $x_i,y_i,t_i$，表示在 $t_i$ 时刻，第 $i$ 个地鼠出现了，它探出头的位置是 $(x_i,y_i)$。

输出格式

砸到 $k$ 个地鼠最少需要花费多少金币？ 如果无法完成任务，输出 -1 。

2 2
3 5 10
6 6 13

-1

5 2
1 7 12
6 6 15
8 9 20
8 4 21
12 23 999

16

提示

• 样例数据1解释 玩家首先花费 $8$ 金币在第八秒到达 $(3,5)$，第十秒砸掉第一个地鼠，但是玩家还需要花费 4 秒时间到达 $(6,6)$，第十四秒第二只地鼠已经消失，无法完成任务。
• 样例数据2解释 玩家选择砸掉第二个地鼠和第四个地鼠，最少花费 $16$ 金币。