Nurie

Paper has $n$ circles drawn on it. A rabbit has $k$ colors of paint and colors the paper following these rules.

• Each region is either painted with one color of paint or left unpainted. A region is a part of finite area bounded by a set of arcs.
• Two adjacent regions cannot be painted with the same color. Two regions are adjacent when an arc is shared by part of their boundaries. Two regions that share only finitely many points are not adjacent.
• Leaving two adjacent regions both unpainted is allowed.

The rabbit wants to paint as many regions as possible. Find the maximum number of regions that can be painted.

The first line contains $n$ and $k$ ($1 \le n \le 20$, $1 \le k \le 10^9$). Each of the next $n$ lines contains integers $x_i$, $y_i$, $r_i$ ($-1000 \le x_i, y_i \le 1000$, $1 \le r_i \le 1000$). No two circles coincide.

No two distinct points within distance $10^{-3}$ of each other are among the intersection points of any two circles.

Print the maximum number of regions that can be painted, on one line.