N circles are drawn on the paper. The rabbit has k-colored paint and paints the paper according to the following rules.

* Paint each area with one color of paint or nothing. Here, the "area" refers to the part with a finite area surrounded by a set of arcs.
* Two adjacent areas cannot be painted with the same color. Here, "adjacent" means that there is an arc that shares a part of the boundary. There are a finite number of shared points. Two areas are not considered to be adjacent.
* It is permissible to leave both adjacent areas unpainted.



Rabbit wants to paint as many areas as possible. Find the maximum number of areas that can be painted.



Input

Line 1: n k (1 ≤ n ≤ 20, 1 ≤ k ≤ 1 000 000 000)
Line 2- (n + 1): xi yi ri, (-1 000 ≤ xi, yi ≤ 1 000, 1 ≤ ri ≤ 1 000) (integer)

Neither two circles match.

The point set obtained as the intersection of any two circles does not include two different points with a distance of 10-3 or less.

Output

Output the maximum number of areas that can be painted with paint on one line.

Example

Input

2 1
10 0 10
20 0 10


Output

2

Source: aizu | Difficulty: UNKNOWN_DIFFICULTY


Solutions: