#include <iostream>
#include <algorithm>
using namespace std;
struct Beast {
int a;
int b;
};
struct Power {
int k;
int p;
};
void offense_min(int& min, int& sum, int& t, int& h, bool& temp, Beast bea, Power repow[]) {
for (;h<t;)
{
bea.a -= repow[h].p - bea.b;
sum += repow[h].k;
h++;
offense_min(min, sum, t, h, temp, bea, repow);
if (bea.a <= 0) {
if (temp) { min = sum; temp = false;}
if (sum<min)
min = sum;
}
sum-=repow[h].k;
}
}
int main() {
int n, m;
cin >> n >> m;
Beast *bea = new Beast[n];
Power *pow = new Power[m];
Power repow[1000];
for (int i = 0; i<n; i++)
cin >> bea[i].a >> bea[i].b;
for (int i = 0; i<m; i++)
cin >> pow[i].k >> pow[i].p;
for (int i = 0; i<n; i++) {
int min = 0, t = 0, sum = 0, h = 0;
for (int j = 0; j<m; j++) {
if (pow[j].p>bea[i].b) {
repow[t].k = pow[j].k;
repow[t].p = pow[j].p;
t++;
}
}
if (t == 0) cout << \"-1\";
else {
bool temp = true;
offense_min(min, sum, t, h, temp, bea[i], repow);
cout << min;
}
}
delete[] bea;
delete[] pow;
return 0;
}
