E. День рождения
ограничение по времени на тест
4 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Сейчас у Ани День рождения. Она позвала много гостей и приготовила для них один большой (почти бесконечный) праздничный торт, украшенный n кружочками банана разных размеров. Через 7 минут у Маши тоже будет День рождения, а пока Аня старше, она решила немного покомандовать. Она велела Маше разрезать торт k прямолинейными разрезами на несколько частей (разрезы могут пересекаться). В результате кружочки банана разделятся на кусочки.

Гостей у Ани много, и она хочет, чтобы каждому достался хотя бы один кусочек банана с торта. Поэтому она велела Маше сделать максимально возможным суммарное количество кусочков банана, на которые разрежутся кружочки банана. Не страшно, если некоторые кусочки банана окажутся на одном куске торта — главное, чтобы общее число кусочков банана было наибольшим. Определите, какого результата удастся достичь Маше.

Входные данные

В первой строке даны два целых числа n и k — количество кружочков банана и количество разрезов, которые требуется сделать Маше (1 ≤ n ≤ 1000, 1 ≤ k ≤ 105). В следующих n строках заданы местоположение и размеры кружочков банана, которые имеют форму кругов. На торте задана декартова система координат. В каждой строке находятся три целых числа x, y и r — координаты центра соответствующего кружочка банана и его радиус ( - 1000 ≤ x, y ≤ 1000, 1 ≤ r ≤ 1000).

Гарантируется, что кружочки банана не пересекаются, не касаются и не накладываются друг на друга.

Претест 10 — большой тест с n = k = 1000.

Выходные данные

Выведите единственное целое число — наибольшее количество кусочков банана, которое может получиться у Маши после k прямолинейных разрезов.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
1 1
0 0 1
Выходные данные
2
Входные данные
3 1
0 0 1
3 0 1
6 0 1
Выходные данные
6
Входные данные
1 3
0 0 1
Выходные данные
7