#include <iostream>
#include <fstream>
using namespace std;

int main()
{   ifstream f("cufar.in");
    ofstream g("cufar.out");
int p,n,i,d,j,S,k;

bool ciur[1000000];
f>>p>>n;
S=0;
for(d=2; d*d <= 1000000 ; d++)
{
    if(ciur[d]==0)
       {

        for(i=d*d;i<=1000000;i=i+d)
            {ciur[i]=1;
            }
       }
}

for(i=0;i<n;i++)
{
   f>>j;
   f>>k;
   for(d=2;d<j/2;d++)
   {   if(j%d==0)
       {if(ciur[d]==0)
        {k--;

        }
       if(k==0)
       {
           if(p==1)
            g<<d;
            else
            {S=S+d;

            }
            d=j/2;
       }
       }
   }

}
if(p==2)
{
    g<<S;
}



    return 0;
}