Nurie

Time Limit : 1 sec, Memory Limit : 65536 KB

Problem G: Nurie

紙の上に円がn 個書かれている. うさぎはk 色の絵の具を持っていて, 次のルールに従って紙に色を塗っていく.

  • 各領域をある1 色の絵の具で塗るか, 何も塗らない. ここで「領域」とは, 円弧の集合で囲まれた面積有限の部分を指す.
  • 隣り合っている2 つの領域を同じ色の絵の具で塗ることはできない. ここで「隣り合っている」とは,境界の一部を共有する円弧があることを指す. 共有点が有限個である2 つの領域は, 隣り合っているとはみなされない.
  • 隣り合っている2 つの領域の両方を塗らないままにすることは許される.

うさぎはできるだけ多くの領域を絵の具で塗りたい. 塗れる領域の個数の最大値を求めよ.

Input

1 行目: n k (1 ≤ n ≤ 20, 1 ≤ k ≤ 1 000 000 000)
2-(n + 1) 行目: xi yi ri, (−1 000 ≤ xi, yi ≤ 1 000, 1 ≤ ri ≤ 1 000) (整数)

どの2 つの円も一致しない.

いずれか2 円の交点として得られる点集合は, 距離が10−3 以下の異なる2 点を含まない.

Output

絵の具で塗れる領域の個数の最大値を一行に出力せよ.

Sample Input 1

2 1
10 0 10
20 0 10

Sample Output 1

2

Source: ACM-ICPC Japan Alumni Group Summer Camp 2010 , Day 3, Tokyo, Japan, 2010-09-19
http://acm-icpc.aitea.net/