Qutuların qablaşdırılması
Жараsxan Facegle-də çox işləyir. Amma biz KBTU Open 2021-i yazda elan etdikdən sonra, hazırlıqlara kömək etmək üçün Almatıya qayıtmağa qərar verdi. Ənənəvi olaraq, insanlar xaricə gedəndə hədiyyələr gətirirlər. Beləliklə, Жараsxan n qutu hazırladı, burada i-ci qutunun ölçüsü a[i] * b[i] (hündürlük nəzərə alınmır), belə ki, n nəfər xoşbəxt olsun.
Məlum olur ki, hava nəqliyyatı qaydalarına görə bir uçuşda bir nəfərə k qutudan çox götürməyə icazə verilmir. Жараsxanın düşündüyü şey budur ki, əgər ölçülər uyğun gəlirsə, bir qutunu digər qutunun içinə yerləşdirə bilər (əşyalar sonra ən dərin qutuya yerləşdirilir). Məsələn, əgər 3 qutu 2 * 2, 2 * 4 və 5 * 5 ölçülərindədirsə, birincini ikincinin içinə, sonra isə ikincini (artıq birincini ehtiva edən) üçüncünün içinə yerləşdirə bilər. Təhlükəsizlik məqsədilə Жараsxan iki ayrı qutunu bir qutunun içinə yerləşdirə bilməz (amma bir qutunu, içində qutu olan bir qutunu, içində qutu olmayan başqa bir qutunun içinə yerləşdirə bilər). Bu, matryoşkaya çox bənzəyir.
Жараsxana hava nəqliyyatı qaydalarını nəzərə alaraq mümkün qədər çox insanı xoşbəxt etməyə kömək edin.
Giriş məlumatları
Birinci sətir iki tam ədəd n və k (1 ≤ n ≤ 10^5, 1 ≤ k ≤ 100) ehtiva edir.
Növbəti n sətirdə i-ci sətir iki tam ədəd a[i] və b[i] (1 ≤ a[i], b[i] ≤ 10^9) ehtiva edir.
Çıxış məlumatları
Tək bir tam ədəd çıxarın - Жараsxanın bütün k qutuları qablaşdıraraq özü ilə götürə biləcəyi maksimum qutu sayı.