U542947 第一章：新生群落

#### 第一章：新生群落 $\,\,\,\,\,\,\,\,\,$ 现在是地下蚁国刚从神树族分出这一脉，来到地表准备下挖到达目标地点的时候，蚂蚁们需要在惆怅的黄昏时分的到来前，护送蚁后到达目标地点。 $\,\,\,\,\,\,\,\,\,$ 作为神树族的元老"[神树族·跪求一死](https://discourse.xinyoudui.com/u/yhxyd0104/activity)"，它手中掌握着一股数量庞大的兵蚁部队。放哨蚁已经侦查好了地下的情况，所以今天，就是下入地表之时！目前调用的兵蚁不多，只有五只全异巨首蚁（膜翅目-蚁科-盲切叶蚁属，特点是头部巨大，擅长力量性战斗，参考等级Lv.1）和三只木栖举腹蚁（膜翅目-蚁科-举腹蚁属，可以喷射短距离蚁酸，尾部像蜜蜂的针有毒，在树木上栖息，文中只是暂时调动，不会影响生活，Lv.3） $\,\,\,\,\,\,\,\,\,$ 刚下入地表，就遇到了一只Lv.0的蝉幼虫，蚂蚁们不愿打扰它，便从旁边绕过。 $\,\,\,\,\,\,\,\,\,$ 突然，一只圆蛛被挖了出来，它愤怒的一下咬向了一只全异巨首蚁。被袭击的蚂蚁慌乱中没分清方向，还好跪求一死敏锐的感觉到，并释放了信息素，木栖举腹蚁立刻扬起腹部，射出蚁酸。圆蛛感受到了威胁，也射出了蛛丝，一只木栖举腹蚁被射中，就此殒命。 $\,\,\,\,\,\,\,\,\,$ 跪求一死知道不一定打得过，它让五只全异巨首蚁先护送蚁后走，自己和两只木栖举腹蚁战斗，它使出了特化蚁橙绒蚁（一种无翅的蜂类，可以射出毒刺，Lv.4）特化蚁是神树族的底牌，是不同厉害的蚂蚁，跪求一死可以使用它们的绝招）的绝招，射出几根飞刺，像机关枪一样开火。圆蛛至少为Lv.5，他左躲右闪，没有被打中，但已无力反击。 $\,\,\,\,\,\,\,\,\,$ 跪求一死使出了杰克跳蚁（膜翅目-蚁科-斗牛犬蚁亚科-斗牛犬蚁属，擅长跳跃，Lv.7）的绝招，它扑到圆蛛上，一口咬向受惊的圆蛛，在瞬间卸下了一条腿，击杀了圆蛛。 $\,\,\,\,\,\,\,\,\,$ 蚁后安全地在地下安家，地下蚁国的故事，就此开始！

$\,\,\,\,\,\,\,\,\,$ 地下是一个`n·n`的矩形，有`a`只敌性昆虫，分布在`x[i],y[i]`上的每只昆虫的战力值为`b[i]`（即需要`b[i]`只兵蚁才能击败），不过我方有`t`只兵蚁。问：在可以击败路径上的所有昆虫的情况下，从`[1][1]`到`[n][n]`的最短路径为多少？

$\,\,\,\,\,\,\,\,\,$ 第一行`3`个整数：范围`n`,敌性昆虫只数`a`和我方兵蚁数量`t`； $\,\,\,\,\,\,\,\,\,$ 接下来`a`行，每行`3`个整数：坐标`x[i],y[i]`和战力值`b[i]`。

$\,\,\,\,\,\,\,\,\,$ 一行，一个整数表示最短路径。

$\,\,\,\,\,\,\,\,\,$ 数据范围： $\,\,\,\,\,\,\,\,\,$ `1