解题思路

槽位模型与前缀容量

• 目标：让某个“空点”P 的光照等级 ≥ L，且 P 不能放照明塔。
• 半径为 r 的照明塔中心必须落在以 P 为中心、切比雪夫半径 r 的正方形网格内，但需要排除中心点 P 本身。 可用槽位：$S'(r)=(2r+1)^2-1=4r^2+4r$。
• 因为“每个坐标最多放一个照明塔”，并且半径允许的区域是嵌套的，所以可行当且仅当对所有 D， 已选“半径 ≤ D”的数量 ≤ $S'(D)$。

题目内容

小 A 是一个喜欢玩电子游戏的人。他今天接触到了一款名为 $FS$ 的新游戏，在这个游戏中，有一个无穷大的坐标网格地图，在这个游戏的夜间模式中，玩家需要建造若干照明塔来为地图照明，具体地，小 A 随时可以在 $(a,b)$ 处建造一个光照半径为 $r$ 的照明塔，建造完成后所有满足 $max(丨x-a丨,丨y-b丨) <=r$ 的点 $(x,y)$ 处的光照等级都会加 $1$ (请注意这里是切比雪夫距离小于等于 $r$ 而非欧几里得距离，初始时所有位置的光照等级均为 $0$ )。

小 A 现在希望达成 $FS$ 游戏中的一项成就，叫做“灯火通明”。具体而言，玩家需要使某一空点处(即该坐标处没有照明塔)的光照等级增加到至少 $L$ 。

小 A 可以通过建造多个照明塔来达到这一目的。在当前模式下有 $n$ 种照明塔可供建造，第 $i$ 种照明塔的光照半径为 $r_i$ ，造价为 $v_i$ ，且至多能建造 $a_i$ 座。

小 A 想知道达成这一成就至少需要花费多少钱，或者判断在当前模式下是否无法达成这一成就。

清注意，照明塔只能放置于整数坐标，且一个坐标处至多只能放置一个照明塔。

输入描述

本题单个测试点包含多组测试数据，输入数据第一行为数据组数 $T(1<=T<=10^4)$ 。

每组的第一行包含两个整数 $n(1<=n<=10^5)$ 和 $L(1<=L<=10^{12})$ ，表示小 A 可以建造的照明塔的种类数和达成成就所需的光照等级。

接下来 $n$ 行每行包含三个整数 $r_i、v_i$ 和 $a_i(1<=r_i<=n，1<=v_i<=10^5，1<=a_i<=10^9)$ ，含义如上文所示。

数据保证对于单个测试数据，所有 $v_i$ $a_i$ 的和不会超过 $10^{18}$ 。测试点内所有测试数据 $n$ 之和不会超过 $2×10^5$ 。

输出描述

如果小 A 可以在当前模式下达成《灯火通明》成就，则输出最小所需花费，否则输出 $-1$ 。

请注意答案可能会超过 $32$ 位有符号整形数所能表示的最大范围。

样例1

输入

2
2 9
1 1 9
2 2 3
2 25
1 1 9
2 2 16

输出

10
-1