1003
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const long long MAXN = 9223372036854775807;
typedef struct beast{
int a;
int b;
}Beast;
typedef struct power{
int k;
int p;
}Power;
//Power powe[1001];
//Beast bea[100001];
long long dp[11][1001][1001];
long long min(long long x, long long y)
{
if (x <= y)
return x;
else
return y;
}
int main()
{
int n, m;
int i, j, k;
int offense;
int count = 0;
// bool vis[100001];
while (scanf("%d%d", &n, &m) != EOF)
{
Beast*bea = (Beast*)malloc(sizeof(Beast)*(n + 1));
Power*powe = (Power*)malloc(sizeof(Power)*(m + 1));
// bool*vis = (bool*)malloc(sizeof(bool)*(n + 1));
for (i = 0; i < n; i++)
scanf("%d%d", &bea[i].a, &bea[i].b);
for (i = 0; i < m; i++)
scanf("%d%d", &powe[i].k, &powe[i].p);
for (k = 0; k <= 10; k++)//k表示防御值
{
for (i = 0; i < m; i++)
{
offense = powe[i].p - k;
for (j = 0; j <= 1000; j++)
{
if (offense <= 0)
{
if (i >= 1)
dp[k][i][j] = dp[k][i - 1][j];
else
dp[k][i][j] = MAXN;
continue;
}
if (i == 0 && j != 0)
{
while (count*offense < j)
{
count++;
}
dp[k][i][j] = count*(powe[i].k);
count = 0;
}
else if (j == 0)
dp[k][i][j] = 0;
else
{
dp[k][i][j] = dp[k][i - 1][j];
if (j >= offense)
dp[k][i][j] = min(dp[k][i][j - offense] + powe[i].k, dp[k][i][j]);
else
dp[k][i][j] = min(powe[i].k, dp[k][i][j]);
}
}
}
// printf("%I64d\n", dp[m - 1][bea[k].a]);
}
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)//和所有晶石攻击大小比较
{
if (bea[i].b < powe[j].p)
break;
}
if (j==m)
printf("-1\n");
else
printf("%lld\n", dp[bea[i].b][m - 1][bea[i].a]);
}
}
// system("pause");
return 0;
}
