#include <iostream>
#include <fstream>

using namespace std;

ifstream in("cufar.in");
ofstream out("cufar.out");

int n, p, ciur[1000001], x, maxim, prime[1000001], k;
long long S;
pair<int, int> v[1000001];

void find_prime(){
    ciur[0] = 1;
    ciur[1] = 1;
    for(int i = 2; i<=maxim; i++){
        if(ciur[i] == 0){
            prime[++k] = i;
            for(int j = 2; i * j <=maxim; j++)
                ciur[i*j] = 1;
        }
    }
}

int main(){
    in >> p >> n;
     for(int i = 1; i<=n; i++){
            in >> v[i].first >> v[i].second;
            if(v[i].first > maxim) maxim = v[i].first;
        }
    find_prime();
    for(int i = 1; i<=n; i++){
        int aux = 0;
        int j = 1;
        for(j; j<=v[i].first && aux!=v[i].second; j++)
            if(v[i].first % prime[j] == 0) aux++;
        if(aux == v[i].second && p == 1) out << prime[j-1] << endl;
        else S+=prime[j-1];
    }
    if(p == 2) out << S;
    return 0;
}