# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* suchit_07

*tabr*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

1315

# PREREQUISITES:

None

# PROBLEM:

Starting with the set S = \{1, 2, \ldots, N\}, you’d like to reach its subset Q.

To do so, you can perform the following move:

- Choose an integer 1 \leq x \leq N, and delete the smallest multiple of x from S.

The cost of doing so is x.

Find the maximum cost required to turn S into Q.

# EXPLANATION:

Let D be the set of elements we need to delete - that is, D = \{1, 2, 3, \ldots, N\} \setminus Q.

For each x \in D, we need to choose a factor of it to delete it.

Given that our aim is to maximize the cost, obviously the best we can do is to choose x itself!

This means the answer is simply the sum of the elements of D.

Note that D has size N - M, and N can be quite large.

So, it’s not really possible to iterate across all the elements.

Instead, notice that D and Q together have all the elements \{1, 2, \ldots, N\}.

So, we know that

The elements of Q are given in the input, so computing their sum is easy.

Further, there’s the well-known formula 1 + 2 + \ldots + N = \frac{N\cdot (N+1)}{2}.

So, the answer is:

Note that the answer can exceed the range of 32-bit integers, so make sure to use larger datatypes such as `long long`

(C++) or `Long`

(Java).

# TIME COMPLEXITY

\mathcal{O}(M) per testcase.

# CODE:

## Author's code (C++)

```
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int N, M;
cin >> N >> M;
vector<int> Q(M);
long long s = 0;
for (int& i : Q)
cin >> i, s += i;
long long ans = (N * 1LL * (N + 1)) / 2;
ans -= s;
cout << ans << '\n';
}
return 0;
}
```

## Editorialist's code (Python)

```
for _ in range(int(input())):
n, m = map(int, input().split())
a = list(map(int, input().split()))
print(n*(n+1)//2 - sum(a))
```