Жарасхан много работает в Facegle. Но после того, как мы анонсировали KBTU Open 2021 весной, он решил возвратиться в Алматы чтобы помочь в подготовке. Традиционно, когда люди приезжают за границу, они привозят подарки. Итак, Жарасхан приготовил n коробок, i - ую размером a[i]
* b[i]
(высота не имеет значения), чтобы n людей стали счастливыми.
Оказывается, правила воздушного транспорта не допускают больше k ящиков на человека за рейс. Что придумал Жарасхан, так это то, что он может класть коробку в другую коробку (предметы затем помещаются в самую глубокую коробку), если подходят размеры. Например, если имеются 3 коробки 2 * 2, 2 * 4 и 5 * 5, он может поместить первую во вторую, а затем вторую (которая уже содержит первую) внутрь третьей. В целях безопасности Жарасхан не может поместить два отдельных ящика в один ящик (но может помещать ящик, содержащий ящик, в другой ящик, который не содержит ящика). Очень похоже на матрешку.
Помогите Жарасхану сделать счастливыми как можно больше людей, зная правила перевозки воздушным транспортом.
Первая строка содержит два целых числа n и k (1 ≤ n ≤ 10^5
, 1 ≤ k ≤ 100).
В следующих n строках i-ая строка содержит два целых числа a[i]
и b[i]
(1 ≤ a[i]
, b[i]
≤ 10^9
).
Выведите единственное целое число - максимальное количество ящиков, которое Жарасхан может взять с собой, упаковав все k ящиков.