Вам задан первоначально пустой неориентированный граф из \(n\) вершин, пронумерованных от \(1\) по \(n\) (т. е. \(n\) вершин и \(0\) ребер). Вы хотите добавить в него \(m\) ребер так, чтобы граф не содержал петель и кратных ребер.
Если будет добавлено ребро, соединяющее две вершины \(u\) и \(v\), его вес должен быть равен наибольшему общему делителю \(u\) и \(v\), т. е. \(\gcd(u, v)\).
Для того чтобы добавлять ребра в граф, вы можете повторять следующую операцию произвольное количество раз (возможно, ни разу):
- выбираете целое число \(k \ge 1\);
- добавляете ровно \(k\) ребер в граф, каждое веса \(k + 1\). Добавление этих \(k\) ребер суммарно стоит \(k + 1\).
Заметим, что вы не можете создавать петли или кратные ребра. А потому, если вы не можете добавить
\(k\) ребер веса
\(k + 1\), вы не можете выбрать такое
\(k\).
Например, если вы можете добавить еще \(5\) ребер веса \(6\), вы можете их добавить в граф, и добавление будет стоить \(6\) за всю группу из \(5\) ребер. Однако если вы можете добавить только \(4\) ребра веса \(6\) в граф, вы не можете выполнить данную операцию для \(k = 5\).
Для заданных \(n\) и \(m\), посчитайте минимальную суммарную стоимость создания графа из \(n\) вершин и ровно \(m\) ребер, используя описанную выше операцию. Если построить такой граф нельзя, выведите \(-1\).
Заметим, что результирующий граф может состоять из нескольких компонент связности.
Примечание
В первом наборе входных данных, мы можем добавить одно ребро между вершинами \(2\) и \(4\) с \(\gcd = 2\). Это единственный способ добавить \(1\) ребро, и он будет стоить \(2\).
Во втором наборе, невозможно добавить \(10\) ребер, а потому ответ \(-1\).
В третьем наборе, мы можем добавить следующие ребра:
- \(k = 1\): ребро веса \(2\) между вершинами \(2\) и \(4\) (\(\gcd(2, 4) = 2\)). Стоимость: \(2\);
- \(k = 1\): ребро веса \(2\) между вершинами \(4\) и \(6\) (\(\gcd(4, 6) = 2\)). Стоимость: \(2\);
- \(k = 2\): ребра веса \(3\): \((3, 6)\) и \((3, 9)\) (\(\gcd(3, 6) = \gcd(3, 9) = 3\)). Стоимость: \(3\).
В результате мы добавили
\(1 + 1 + 2 = 4\) ребра с общей стоимостью
\(2 + 2 + 3 = 7\), что является оптимальным ответом.