Nurie

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

inputFormat

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.

outputFormat

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

样例

2 1
10 0 10
20 0 10

2