#include<bits/stdc++.h>
using namespace std;
void solve()
{long long n,m;
cin>>n>>m;
long long arr[n]={0};
while(m--)
{
long long x,y;
cin>>x>>y;
for(long long i=0;i<n;i++)
{
if((i+1)%y!=0 && arr[i]<x)
{
arr[i]=x;
}
}
}
long long sum=0;
for(long long i=0;i<n;i++)
{
sum=sum+arr[i];
}
cout<<sum<<endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long t;
cin >> t;
while(t--){
solve();
}
return 0;
}