E. Төрсөн өдөр

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Өнөөдөр Аннагийн төрсөн өдөр! Тэр маш олон зочдыг үдэшлэгтээ уриад $n$ ширхэг ялгаатай гадлийн тойргоор чимэглэсэн аварга том бялуу бэлджээ. Одоо харин Мариягийн төрсөн өдөр болоход 7 минут дутуу байв. Тиймээс арай ахмад байгаа дээрээ Анна жаахан зарахаар шийдэв. Тэр бялууны гадилийн тойргуудыг хуваахын тулд Мариад яг $k$ шулуун зураасаар хуваах даалгавар өгөв.

Аннагийнд маш олон зочид ирсэн тул тэр хүн бүрт бага ч болтугай гадилийн хэсгээс өгөхийг хүсэж байгаа. Тиймээс тэр Мариаг аль болох олон хэсэгт хуваахыг шаардав. Гадил нь нэг бялууны хэсэг дээр үлдэж болно хамгийн гол нь гадилийг олон хэсэгт хуваах шаардлагатай. Мариад тусла.

Оролт

Эхний мөрөнд $n$ болон $k$ ($1 ≤ n ≤ 1000, 1 ≤ k ≤ 10^5$) тоонууд өгөгдөнө. Дараагийн $n$ мөрөнд гадлийн тойргуудын байршилууд болон радиусууд өгөгдөнө. Мөр бүрт $x, y, r$ тоонууд байрлана ($ - 1000 ≤ x, y ≤ 1000, 1 ≤ r ≤ 1000$).

Гадилийн тойргууд нь хоорондоо огтлолцохгүй мөн шүргэлцэхгүй.

Урьдчилсан тестний 10 дахь $n = k = 1000$ байгаа.

Гаралт

$k$ шулуун зүсэлт хийсэний дараа хамгийн ихдээ хэдэн хэсэг болж хуваагдахыг илэрхийлэх ганц тоог хэвлэ. C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: Энхсанаа

Жишээ тэстүүд

Оролт
1 1
0 0 1
Гаралт
2
Оролт
3 1
0 0 1
3 0 1
6 0 1
Гаралт
6
Оролт
1 3
0 0 1
Гаралт
7
Сэтгэгдлүүдийг ачааллаж байна...