Вам дано натуральное число \(k\) и множество \(S\) всех целых чисел от \(l\) до \(r\) (включительно).
Вы можете выполнять следующую двухшаговую операцию любое количество раз (возможно, ноль):
- Сначала выберите такое число \(x\) из множества \(S\), что в \(S\) есть как минимум \(k\) чисел, кратных \(x\) (включая само \(x\));
- Затем удалите число \(x\) из \(S\) (обратите внимание, что ничего другое не удаляется).
Найдите максимально возможное количество раз, которое можно выполнить данную операцию.
Примечание
В первом наборе входных данных изначально \(S = \{3,4,5,6,7,8,9\}\). Одна возможная оптимальная последовательность операций:
- Выберите \(x = 4\) для первой операции, так как в \(S\) есть два числа, кратных \(4\): \(4\) и \(8\). \(S\) становится равным \(\{3,5,6,7,8,9\}\);
- Выберите \(x = 3\) для второй операции, так как в \(S\) есть три числа, кратных \(3\): \(3\), \(6\) и \(9\). \(S\) становится равным \(\{5,6,7,8,9\}\).
Во втором наборе входных данных изначально \(S=\{4,5,6,7,8,9\}\). Одна возможная оптимальная последовательность операций:
- Выберите \(x = 5\), \(S\) становится равным \(\{4,6,7,8,9\}\);
- Выберите \(x = 6\), \(S\) становится равным \(\{4,7,8,9\}\);
- Выберите \(x = 4\), \(S\) становится равным \(\{7,8,9\}\);
- Выберите \(x = 8\), \(S\) становится равным \(\{7,9\}\);
- Выберите \(x = 7\), \(S\) становится равным \(\{9\}\);
- Выберите \(x = 9\), \(S\) становится равным \(\{\}\).
В третьем наборе входных данных изначально \(S=\{7,8,9\}\). Для каждого \(x\) из \(S\) в \(S\) нет другого числа, кратного \(x\) (кроме самого \(x\)). Поскольку \(k = 2\), вы не можете выполнить никаких операций.
В четвертом наборе входных данных изначально \(S=\{2,3,4,5,6,7,8,9,10\}\). Одна возможная оптимальная последовательность операций:
- Выберите \(x = 2\), \(S\) становится равным \(\{3,4,5,6,7,8,9,10\}\);
- Выберите \(x = 4\), \(S\) становится равным \(\{3,5,6,7,8,9,10\}\);
- Выберите \(x = 3\), \(S\) становится равным \(\{5,6,7,8,9,10\}\);
- Выберите \(x = 5\), \(S\) становится равным \(\{6,7,8,9,10\}\).