CF128E.Birthday

Anna's got a birthday today. She invited many guests and cooked a huge (nearly infinite) birthday cake decorated by n banana circles of different sizes. Maria's birthday is about to start in 7 minutes too, and while Anna is older, she decided to play the boss a little. She told Maria to cut the cake by k straight-line cuts (the cutting lines can intersect) to divide banana circles into banana pieces.

Anna has many guests and she wants everyone to get at least one banana piece. That's why she told Maria to make the total number of banana pieces maximum. It's not a problem if some banana pieces end up on the same cake piece — the key is to make the maximum number of banana pieces. Determine what result Maria will achieve.

安娜今天过生日。她邀请了许多客人，并准备了一个巨大的（近乎无限的）生日蛋糕，蛋糕上装饰着 $n$ 个大小各不相同的香蕉圆圈。玛丽亚的生日也将在 7 分钟后开始；尽管安娜年龄更大，但她想稍稍摆一摆“老板”的架子。于是她让玛丽亚用 $k$ 条直线切割蛋糕（这些切割线可以相交），从而将香蕉圆圈分割成若干香蕉块。

安娜有许多客人，她希望每位客人都至少得到一块香蕉块。因此，她要求玛丽亚使香蕉块的总数尽可能多。某些香蕉块落在同一块蛋糕上也无所谓——关键在于使香蕉块的总数最大化。请确定玛丽亚所能达到的最大结果。

The first line contains two integers n and k — the number of banana circles and the number of cuts Maria should perform (1 ≤ n ≤ 1000, 1 ≤ k ≤ 105). Next n lines contain the positions and sizes of the banana circles (all banana circles are round). On the cake the Cartesian coordinate system is defined. Each line contains three integers x, y and r — the coordinates of the center of the corresponding banana piece and its radius ( - 1000 ≤ x, y ≤ 1000, 1 ≤ r ≤ 1000).

It is guaranteed that the banana circles do not intersect, do not touch each other and do not overlap with each other.

Pretest 10 is big test with n = k = 1000.

第一行包含两个整数 $n$ 和 $k$ —— 分别表示香蕉圆的数量以及玛丽亚应执行的切割次数（$1 \leq n \leq 1000$，$1 \leq k \leq 10^5$）。接下来的 $n$ 行描述了香蕉圆的位置与尺寸（所有香蕉圆均为圆形）。蛋糕上定义了笛卡尔坐标系。每行包含三个整数 $x$、$y$ 和 $r$ —— 分别表示对应香蕉片圆心的坐标及其半径（$-1000 \leq x, y \leq 1000$，$1 \leq r \leq 1000$）。

保证所有香蕉圆互不相交、互不相切，且互不重叠。

预测试用例 10 是一个大规模测试用例，其中 $n = k = 1000$。

Print the only integer — the largest number of banana pieces that Maria can get after she performs the k straight-line cuts.

Please do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specificator.

输出唯一的整数——玛丽亚在进行 k 次直线切割后所能获得的最多香蕉块数。

在 C++ 中，请勿使用 %lld 格式说明符来读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 格式说明符。