安娜今天过生日。她邀请了很多客人,做了一个巨大的(几乎是无限的)生日蛋糕,上面装饰着n个不同大小的香蕉圈。玛丽亚的生日也即将在 7 分钟后开始,虽然安娜年纪较大,但她决定扮演一下老板。她告诉玛丽亚用k条直线切割(切割线可以相交)来切割蛋糕,将香蕉圈分成香蕉块。
安娜有很多客人,她希望每个人都至少得到一块香蕉。这就是为什么她告诉玛丽亚要让香蕉片的总数达到最大。如果一些香蕉片最终出现在同一个蛋糕片上也没有问题——关键是制作尽可能多的香蕉片。确定玛丽亚将取得什么结果。
输入
第一行包含两个整数 n 和 k — 香蕉圈的数量和 Maria 应该执行的切割次数 (1 ≤ n ≤ 1000, 1 ≤ k ≤ 105)。接下来的 n 行包含香蕉圈的位置和大小(所有香蕉圈都是圆形的)。在蛋糕上定义了笛卡尔坐标系。每行包含三个整数 x、y 和 r——相应香蕉片的中心坐标及其半径(- 1000 ≤ x,y ≤ 1000,1 ≤ r ≤ 1000)。
保证香蕉圈不相交、不互相接触、不互相重叠。
预测试 10 是一个大测试,n = k = 1000。
输出
打印唯一的整数——玛丽亚执行 k 次直线切割后可以获得的最大香蕉片数。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 指定器。
示例
输入 #1
1 1 0 0 1
输出 #1
2
输入 #2
3 1 0 0 1 3 0 1 6 0 1
输出 #2
6
输入 #3
1 3 0 0 1
输出 #3
7