У вас есть множество \(S\), состоящее из \(n\) наименьших положительных целых чисел: \(1, 2, \ldots, n\).
Вы можете выполнить следующую операцию на \(S\) несколько раз (возможно, ноль):
- Выберите положительное целое число \(k\) такое, что \(1 \le k \le n\), и в множестве \(S\) есть хотя бы одно число, кратное \(k\). Затем удалите наименьшее кратное \(k\) число из \(S\). Стоимость такой операции равна \(k\).
Вам дано множество \(T\), являющееся подмножеством \(S\). Найдите минимальную возможную суммарную стоимость операций, необходимых, чтобы множество \(S\) превратить в \(T\). Можно показать, что это всегда возможно сделать.
Примечание
В первом наборе входных данных не нужно выполнять никаких операций, так как \(S\) уже равно \(T\), т. е. множеству \(\{1, 2, 3, 4, 5, 6\}\).
Во втором наборе изначально \(S = \{1, 2, 3, 4, 5, 6, 7\}\), а \(T = \{1, 2, 4, 7\}\). Нужно выполнить следующие операции:
- Выберите \(k=3\), удалите \(3\) из \(S\).
- Выберите \(k=3\), удалите \(6\) из \(S\).
- Выберите \(k=5\), удалите \(5\) из \(S\).
Общая стоимость равна \(3+3+5 = 11\). Можно показать, что это минимально возможная стоимость.
В третьем примере изначально \(S = \{1, 2, 3, 4\}\), а \(T = \{\}\) (пустое множество). Можно выполнить \(4\) операции с \(k=1\), чтобы удалить \(1\), \(2\), \(3\) и \(4\).
В четвертом примере изначально \(S = \{1, 2, 3, 4\}\), а \(T = \{3\}\). Можно выполнить две операции с \(k=1\) для удаления \(1\) и \(2\), а затем выполнить одну операцию с \(k=2\) для удаления \(4\).