Упакування коробок#10641
Жарасхан багато працює у Facegle. Але після того, як ми анонсували KBTU Open 2021 навесні, він вирішив повернутися до Алмати, щоб допомогти у підготовці. Традиційно, коли люди приїжджають з-за кордону, вони привозять подарунки. Отже, Жарасхан приготував коробок, де -та коробка має розміри a_i \times b_i (висота не має значення), щоб зробити людей щасливими.
Виявляється, правила повітряного транспорту не дозволяють перевозити більше ніж коробок на людину за один рейс. Жарасхан придумав, що він може вкладати одну коробку в іншу (предмети тоді розміщаються в найглибшій коробці), якщо розміри підходять. Наприклад, якщо є коробки розміром 2 \times 2, 2 \times 4 і 5 \times 5, він може помістити першу в другу, а потім другу (яка вже містить першу) всередину третьої. З міркувань безпеки Жарасхан не може покласти два окремі ящики в один ящик (але може вкладати коробку, яка містить інші коробки, у ще одну коробку, яка не містить коробок). Це дуже схоже на матрьошку.
Допоможіть Жарасхану зробити щасливими якомога більше людей, враховуючи правила перевезення повітряним транспортом.
Перший рядок містить два цілих числа і (1 \le n \le 10^5, 1 \le k \le 100).
У наступних рядках -ий рядок містить два цілих числа a_i і b_i (1 \le a_i, b_i \le 10^9).
Виведіть єдине ціле число — максимальну кількість коробок, яку Жарасхан може взяти з собою, упаковуючи їх не більше, ніж у коробок.
Приклад 1
Приклад 2