După ce și-a cumpărat biscuiți, Costy, eroul nostru, ajunge acasă și se apucă de teme. Astfel, dă peste următoarea problemă:

“La o probă de maraton participă N maratonişti. Ştiind că la secunda 0, un maratonist se află la Xi metri de linia de sosire și aleargă cu o viteză de Yi metri/secundă, să se răspundă la Q întrebări de tipul:

• Câți maratonişti au trecut linia de sosire după Qi secunde ? “

Cerința

Ajutați-l pe Costy să răspundă la cele Q întrebări.

Date de intrare

Fișierul maraton.in conține:

• pe prima linie numărul N, reprezentând numărul de maratoniști;
• pe următoarele N linii, câte 2 numere, Xi Yi, reprezentând distanța fată de linia de sosire și viteza fiecărui maratonist;
• pe următoarea linie, numărul Q reprezentând numărul de întrebări;
• pe următoarele Q linii se află câte un număr Qi reprezentând întrebarea i;

Date de ieșire

Fișierul de ieșire maraton.out conţine:

Exemplu

maraton.in

5
100 4
12 3
101 5 
20 1
44 7
4
20
12
7
21

maraton.out

3
2
2
4

Explicație

• La secunda 20 au trecut linia de sosire maratoniștii cu indicii 2, 4, 5.
• La secunda 12 au trecut linia de sosire maratoniștii cu indicii 2, 5.
• La secunda 7 au trecut linia de sosire maratoniștii cu indicii 2, 5.
• La secunda 21 au trecut linia de sosire maratoniștii cu indicii 2, 3, 4, 5.

# include <iostream>
# include <fstream>

# define MAX_X 100000

using namespace std;

ifstream fin("maraton.in");
ofstream fout("maraton.out");

int f[MAX_X + 5];

int main() 
{

    int N , Q , x , y , q , i;

    fin >> N;

    for ( i = 0; i < N; i ++ ) 
    {
        fin >> x >> y;
        f[x / y + ( x % y > 0 )] ++;
    }

    for ( i = 1; i <= MAX_X; i ++ )
        f[i] += f[i - 1];

    fin >> Q;

    for ( i = 0; i < Q; i ++ ) 
    {
        fin >> q;
        fout << f[q] << '\n';
    }

    fin.close();
    fout.close();

    return 0;
}