Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
if K >= sum(A):
  print(0)
  exit()
A.sort(reverse=True)
F.sort()
from math import gcd
def lcm(x, y):
  return (x*y)//gcd(x, y)

f_lcm = 1
for k in range(N):
  f_lcm = lcm(f_lcm, F[k])

portion = [f_lcm//F[k] for k in range(N)]


#print('A:', A)
#print('F:', F)
#print('portion:', portion)
lot = [0 for _ in range(N)]


sa = sum(A) - K
sp = sum(portion)
for k in range(N):
  point = sa*portion[k]//sp
  if point > A[k]:
    lot[k] += A[k]*F[k]
    A[k] = 0
  else:
    lot[k] += point *F[k]
    A[k] -= point
res = sum(A) - K
#print(lot)
#print(A)
#print(res)

while res>0:
  second  = float('inf')
  for k in range(N):
    if A[k] > 0:
      second = min(second, lot[k] + F[k])
  for k in range(N):
    if A[k] > 0:
      if second == lot[k] + F[k]:
        lot[k] += F[k]
        A[k] -= 1
        res -= 1

print(max(lot))

### FIXED CODE ###

from math import ceil
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
if K >= sum(A):
  print(0)
  exit()
A.sort(reverse=True)
F.sort()
lot = []
for k in range(N):
  lot.append((A[k]*F[k], k))
lot.sort(key =  lambda x:x[0],reverse=True)
high = lot[0][0]
#print('A:', A)
#print('F:', F)
#rint(lot)
def binary_search(high):
  low = 0
  mid = (low + high) //2
  while low < high:
    final = False
    mid = (low + high) //2
    #print(low, high, mid)
    if low == high-1:
      final = True
    #print(low, high, mid)
    res = K
    flag = True
    for k in range(N):
      if res < 0:
        break
      else:
        if lot[k][0] <= mid:
          break
        else:
          res -= ceil((lot[k][0]-mid)/F[lot[k][1]])
          continue
    if res < 0:
      flag = False
    #print(flag)
    if flag:
      high = mid
    else:
      if final:
        mid += 1
      low = mid
    #print(low, high, mid)
  #return None
  return mid

print(binary_search(high))
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
A = []
D = [[-1 for _ in range(W)] for _ in range(H)]
q = deque([])
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "#":
            q.append((i, j))
            D[i][j] = 0
    A.append(S)

while q:
    pos = q.popleft()
    py, px = pos[0], pos[1]
    for (y, x) in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        ny = py + y
        nx = px + x
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if D[ny][nx] < 0:
            D[ny][nx] = D[py][px] + 1
            q.append((ny, nx))

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, D[i][j])
print(ans)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
A = []
D = [[-1 for _ in range(W)] for _ in range(H)]
q = deque([])
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "#":
            q.append((i, j))
            D[i][j] = 0
    A.append(S)

while q:
    pos = q.popleft()
    py, px = pos[0], pos[1]
    for (y, x) in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        ny = py + y
        nx = px + x
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if D[ny][nx] < 0:
            D[ny][nx] = D[py][px] + 1
            q.append((ny, nx))

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, D[i][j])
print(ans)
### BUGGY CODE ###

N = int(input())
AN = list((map(int,input().split(" "))))

AN.sort(reverse=True)

num = 0
count = 0

def bbb(ccc):
    ddd = ccc
    while True:
        if ddd == 2:
            return True
        ddd = ddd / 2
        if ddd % 2 != 0:
            return False

while True:

    if len(AN) == 0:
        break

    A = AN.pop(num)

    for i in range(len(AN)):
        n = A + AN[i]
        if (n & (n - 1) == 0):
            AN.pop(i)
            count += 1
            break

print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split(" ")))
A.sort()
used = [0] * N
pow2_set = reversed([ 1<<i for i in range(36)])
ans = 0
for pow2 in pow2_set:
    l,r = 0,N-1
    while l < r:
        if A[l] + A[r] < pow2:
            l += 1
        elif A[l] + A[r] == pow2:
            if used[l] == 0 and used[r] == 0:
                ans += 1
                used[l],used[r] = 1,1
            else:
                if used[l] == 1:
                    l += 1
                if used[r] == 1:
                    r -= 1
        else:
            r -= 1
 
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(n: int, v: "List[int]"):
    e = [(len(v[0::2]) - vv, k, 0) for k, vv in Counter(v[0::2]).items()]
    o = [(len(v[1::2]) - vv, k, 1) for k, vv in Counter(v[1::2]).items()]

    res = [(len(v[0::2]),''), (len(v[1::2]),'')]
    for n, k, t in sorted(e + o):
        if res[t][1] != '':
            continue

        if res[1 - t][1] == k:
            continue

        res[t] = (n, k)
        if res[0][1] != '' and res[1][1] != '':
            break
    return res[0][0] + res[1][0]


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    v = [ int(next(tokens)) for _ in range(n) ]  # type: "List[int]"
    result = solve(n, v)
    print(result)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(n: int, v: "List[int]"):
    e = v[0::2]
    o = v[1::2]

    ec = sorted([(vv, k) for k, vv in Counter(e).items()], reverse=True) + [(0, None)]
    oc = sorted([(vv, k) for k, vv in Counter(o).items()], reverse=True) + [(0, None)]

    ee1 = ec[0]
    oo1 = oc[1] if oc[0][1] == ee1[1] else oc[0]
    ret1 = len(v) - ee1[0] - oo1[0]

    oo2 = oc[0]
    ee2 = ec[1] if ec[0][1] == oo2[1] else ec[0]
    ret2 = len(v) - ee2[0] - oo2[0]
   
    return min(ret1, ret2)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    v = [ int(next(tokens)) for _ in range(n) ]  # type: "List[int]"
    result = solve(n, v)
    print(result)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys

input = sys.stdin.readline

N, W = map(int, input().split())

dp = [0] * (W + 1)

for _ in range(N):
    w, v = map(int, input().split())
    for wk in range(W, w-1, -1):
        tv = dp[wk - w] + v
        if tv > dp[wk]:
            dp[wk] = tv

print(dp[-1])

### FIXED CODE ###


import sys

input = sys.stdin.readline

N, W = map(int, input().split())

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    A=[[INF]*n for _ in range(n)]
    for _ in range(m):
        a,b=map(int,input().split())
        a-=1; b-=1;
        A[a][b]=1
    next=[list(range(n)) for _ in range(n)]
    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        if(A[i][j]>A[i][k]+A[k][j]):
            A[i][j]=A[i][k]+A[k][j]
            next[i][j]=next[i][k]
    length=n+1
    v=-1
    for i in range(n):
        if(length>A[i][i]):
            length=A[i][i]
            v=i
    if(v==-1):
        print(-1)
        return
    print(length)
    print(v+1)
    u=next[v][v]
    while(u!=v):
        print(u+1)
        u=next[u][v]
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        a,b=map(lambda x:int(x)-1,input().split())
        E[a].append(b)

    # bfs
    def bfs(sv):
        prev=[-1]*n
        flag=False
        from collections import deque
        Q=deque([sv])
        while(Q):
            v=Q.popleft()
            for nv in E[v]:
                if(nv==sv):
                    flag=True
                    break
                elif(prev[nv]==-1):
                    prev[nv]=v
                    Q.append(nv)
            if(flag): break
        if(not flag):
            return [0]*(n+1)
        else:
            loop=[]
            while(v!=-1):
                loop.append(v)
                v=prev[v]
            loop.reverse()
            return loop

    # calculate
    ans=[0]*(n+1)
    for i in range(n):
        loop=bfs(i)
        if(len(loop)<len(ans)):
            ans=loop
    if(len(ans)==n+1):
        print(-1)
    else:
        print(len(ans))
        for v in ans: print(v+1)
resolve()
### BUGGY CODE ###

N=int(input())
A= list(map(int,input().split()))
ans=0
for i in range(N):
    for j in range(i+1, N):
        ans+=A[i]*A[j]
print(ans%(10**9+7))

### FIXED CODE ###

N=int(input())
A= list(map(int,input().split()))
ans=0
S=sum(A)
for i in range(N):
    S-=A[i]
    ans+=A[i]*S
print(ans%(10**9+7))
### BUGGY CODE ###

MOD = 998244353


def main():
    N, S = map(int, input().split())
    A = list(sorted(map(int, input().split())))
    prev = {(0, 0): 1}
    for i in range(N):
        cur = {k: prev[k] for k in prev}
        for num, total in prev:
            if total + A[i] > S:
                continue
            key = (num+1, total + A[i])
            if key in cur:
                cur[key] = cur[key] + prev[(num, total)]
            else:
                cur[key] = prev[(num, total)]
        prev = cur
    ans = 0
    for num in range(1, N+1):
        if (num, S) in cur:
            ans = (ans + cur[(num, S)] * pow(2, N-num, MOD)) % MOD
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

MOD = 998244353


def main():
    N, S = map(int, input().split())
    A = list(sorted(map(int, input().split())))
    prev = [0] * (S+1)
    prev[0] = pow(2, N, MOD)
    half = pow(2, MOD-2, MOD) % MOD
    for i in range(N):
        cur = list(prev)
        for total in range(S+1):
            if total + A[i] > S:
                continue
#            key = encode(num+1, total + A[i], S)
            cur[total + A[i]] = (cur[total + A[i]] +
                                 prev[total] * half) % MOD
        prev = cur
    print(cur[S])


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(20000000)
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    ans = [[0, deque()] for _ in range(N)]

    for _ in range(N - 1):
        p, c = map(int, input().split())
        ans[p-1][1].append(c-1)
        ans[c-1][1].append(p-1)

    for _ in range(Q):
        p, v = map(int, input().split())
        ans[p-1][0] += v

    def add_value(node, parent):
        val = ans[node][0]
        children = ans[node][1]
        for child in children:
            if child == parent:
                continue
            ans[child][0] += val
            add_value(child, node)

    add_value(0, -1)

    print(' '.join([str(x[0]) for x in ans]))


if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import deque

N, Q = map(int, input().split())
edge = [[] for i in range(N)]
ops = []
ans = [0] * N

for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
for _ in range(Q):
    ops.append(tuple(map(int, input().split())))

for op in ops:
    node = op[0] - 1
    pnt = op[1]
    ans[node] += pnt

stack = deque()
stack.append((0, -1))

while stack:
    st = stack.pop()
    node, parent = st[0], st[1]
    children = edge[node]
    for child in children:
        if child == parent:
            continue
        ans[child] += ans[node]
        stack.append((child, node))

print(*ans)
### BUGGY CODE ###

N = int(input())
S = [list(input()) for i in range(N)]
T = ['' for m in range(N)]

for l in range(N):
  S[l].sort()
  T[l] = ''.join(S[l])

ans = 0
for j in range(N-1):
  for k in range(j+1,N):
    p = 0
    x = 1
    while x == 1 and p < 10:
      if S[j][p] != S[k][p]:
        x = 0
        break
      else:
        p += 1
    ans += x

print(ans)

### FIXED CODE ###

from operator import itemgetter
N = int(input())
S = [list(input()) for i in range(N)]

for l in range(N):
  S[l].sort()
  S[l] = ''.join(S[l]) 

S.sort()

X = []
p = 1

for j in range(N-1):
  if S[j] == S[j+1]:
    p +=1
  else:
    X.append(p)
    p = 1
X.append(p)


def comb(n):
  if n == 2: return 1
  else:
    return int(n*(n-1)/2)

ans = 0

for k in range(len(X)):
  ans += comb(X[k])

print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(250000)

import queue

def main():
    n, k = map(int, input().split())
    h = list(map(int,input().split()))

    cost = [sys.maxsize]*n
    cost[0] = 0
    for i in range(0,n):
        for j in range(1, k + 1):
            if (i+ j>= n):
                break
            abs_ = abs(h[i] - h[i+j])
            if cost[i+j] >cost[i] + abs_ :
                cost[i+j] = cost[i] + abs_
    print(cost[n-1])
main()



#
# while True:
#     pair_str = input().split()
#     pair_int = [int(s) for s in pair_str]
#     if pair_int[0] == 0 and pair_int[1] == 0 :
#         break
#     else:
#         input_list.append(pair_int)


# if b > c * 2 :
    #     b_price = c
    #
    # input_array_list = []
    #
    # while True:
    #     input_array = input().split()
    #     if input_array[0] == "0" and input_array[1] == "0":
    #         break
    #     else:
    #         input_array_list.append(input_array)
    #
    # for item in input_array_list:
    #     n = int(item[0])
    #     k_sum = int(item[1])
    #
    #     count = 0
    #     for i in range(1,n + 1- 2):
    #         for j in range(i+1, n + 1 - 1):
    #             for k in range (j+1, n+ 1):
    #                 if i + j + k == k_sum :
    #                     count = count + 1
    #     print(count)

    #
    # for item in input_array_list:
    #     if item[1] == "+":
    #         print(str(int(item[0])+int(item[2])))
    #     elif item[1] =="-":
    #         print(str(int(item[0])-int(item[2])))
    #     elif item[1] == "/":
    #         print(str(int(item[0])//int(item[2])))
    #     elif item[1] == "*":
    #         print(str(int(item[0])*int(item[2])))
    #

# import sympy as sp

# input_list = []
# a,b,c = map(int, input().split())
# divisors = sp.divisors(c)
#
# count = 0
#
# for divisor in divisors:
#     if a <= divisor and divisor <= b:
#         count = count + 1
# print(count)
#
# while True:
#     pair_str = input().split()
#     pair_int = [int(s) for s in pair_str]
#     if pair_int[0] == 0 and pair_int[1] == 0 :
#         break
#     else:
#         input_list.append(pair_int)
#
# for pair_int in input_list:
#     if pair_int[0] <= pair_int[1]:
#         print("{} {}".format(pair_int[0], pair_int[1]))
#     else:
#         print("{} {}".format(pair_int[1], pair_int[0]))

#for i in range(10000):
#    print("Hello World")
#a = input().split()
#a_int = [int(s) for s in a]
#a_sorted = sorted(a_int)
#print(' '.join(map(str, a_sorted)))


### FIXED CODE ###

import sys

sys.setrecursionlimit(250000)
input = sys.stdin.readline
import queue


def main():
    n, k = map(int, input().split())
    h = list(map(int,input().split()))

    cost = [sys.maxsize]*n
    cost[0] = 0
    for i in range(0,n):
        for j in range(1, k + 1):
            if (i+ j>= n):
                break
            abs_ = abs(h[i] - h[i+j])
            if cost[i+j] >cost[i] + abs_ :
                cost[i+j] = cost[i] + abs_
    print(cost[n-1])
main()
### BUGGY CODE ###

import random
A, B = map(int, input().split())
X = [[0] * (10**4) for _ in range(10**5)]
print(A)

### FIXED CODE ###

A, B = map(int, input().split())
print(max(A*2-1,A+B,B*2-1))
### BUGGY CODE ###

def submit():
  n,q = map(int,input().split())
  y = [[] for _ in range(n)]
  c = [0]*n
  for _ in range(n-1):
    ai,bi = map(int,input().split())
    y[ai-1].append(bi-1)
    y[bi-1].append(ai-1)
  for _ in range(q):
    pi,xi = map(int,input().split())
    c[pi-1] += xi
  z = [[0,-1]]
  while z:
    j,b = z.pop(0)
    for yj in y[j]:
      if yj != b:
        z.append([yj,j])
        c[yj] += c[j]
  for i in range(n):
    print(c[i],end=" ")
submit()

### FIXED CODE ###

from collections import deque
def submit():
  n,q = map(int,input().split())
  y = [[] for _ in range(n)]
  c = [0]*n
  for _ in range(n-1):
    ai,bi = map(int,input().split())
    y[ai-1].append(bi-1)
    y[bi-1].append(ai-1)
  for _ in range(q):
    pi,xi = map(int,input().split())
    c[pi-1] += xi
  z = deque([[0,-1]])
  while z:
    j,b = z.popleft()
    for yj in y[j]:
      if yj != b:
        z.append([yj,j])
        c[yj] += c[j]
  for i in range(n):
    print(c[i],end=" ")
submit()
### BUGGY CODE ###

n = int(input())
c = input()
i,j = 0, len(c)-1
count = 0
while i!=j:
    if c[i]=='W' and c[j]=='R':
        i+=1
        j-=1
        count += 1
        continue
    if c[i]=='W' and c[j]!='R':
        j -= 1
        continue
    if c[i]!='W' and c[j]=='R':
        i += 1
    if abs(i-j)==1:
        break
print(count)


### FIXED CODE ###

n = int(input())
c = input()
R = c.count('R')
ans = 0
for i in range(R):
    if c[i]=='W':
        ans += 1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())

P = list(map(int, input().split()))


def CalculateExpectedValu(n):
    bunbo = 1 / n
    ans = 0

    for i in range(1,n+1):
        ans = ans + (i*bunbo)

    return ans

number = 0
CumulativeSum = [0]

for i in P:
    number = number + CalculateExpectedValu(i)
    CumulativeSum.append(number)

ans = 0



for i in range(0 , (len(CumulativeSum)-K)):
    tmpans = CumulativeSum[i+K] - CumulativeSum[i]
    ans = max(ans, tmpans)

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())

P = list(map(int, input().split()))


def CalculateExpectedValu(n):
    bunbo = 1 / n
    ans = 0

    for i in range(1,n+1):
        ans = ans + (i*bunbo)

    return ans

number = 0
CumulativeSum = [0]

for i in P:
    number = number + CalculateExpectedValu(i)
    CumulativeSum.append(number)

ans = 0



for i in range(0 , (len(CumulativeSum)-K)):
    tmpans = CumulativeSum[i+K] - CumulativeSum[i]
    ans = max(ans, tmpans)

print(ans)
### BUGGY CODE ###

N = int(input())
S = [''] * N
for i in range(N):
    S[i] = input()

dic = {'': 1, '': 1}
for i in range(N):
    if S[i] not in dic:
        dic[S[i]] = 1
    else:
        dic[S[i]] += 1

max_kv_list = [kv for kv in dic.items() if kv[1] == max(dic.values())]
max_k_list = sorted([t[0] for t in max_kv_list])

for w in max_k_list:
    print(w)



### FIXED CODE ###

N = int(input())
ss = []
for _ in range(N): ss.append(input())

from collections import Counter

ctr = Counter(ss)
counted = ctr.most_common()
# print(counted)
ans = []
for i in range(len(counted)):
    tup = counted[i]
    if i == 0:
        ans.append(tup[0])
        continue
    if counted[i][1] != counted[i - 1][1]:
        break
    ans.append(tup[0])

ans.sort()
for a in ans: print(a)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

flag= True
ans=1
for i in range(n):
    ans*=a[i]
    if ans>10**18:
        flag=False

if flag:
    print(ans)
else:
    if 0 in a:
        print(0)
    else:
        print(-1)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

flag= True
ans=1
for i in range(n):
    ans*=a[i]
    if ans>10**18:
        flag=False
        break

if flag:
    print(ans)
else:
    if 0 in a:
        print(0)
    else:
        print(-1)
### BUGGY CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))

mod = 998244353

dp = [[0] * (S+1) for i in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp[i+1][j] += 2*dp[i][j]
        dp[i+1][j] = dp[i+1][j] % mod
        if j + A[i] <= S:
            dp[i+1][j+A[i]] += dp[i][j]
            dp[i+1][j+A[i]] = dp[i+1][j+A[i]] % mod

print(dp[N][S])

### FIXED CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))

mod = 998244353

dp = [[0 for j in range(S+1)] for i in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp[i+1][j] += 2*dp[i][j]
        dp[i+1][j] %= mod
        if j + A[i] <= S:
            dp[i+1][j+A[i]] += dp[i][j]
            dp[i+1][j+A[i]] %= mod

print(dp[N][S])
### BUGGY CODE ###

S = input()
lst = []

for i in range(len(S)):
    lst.append(int(S[-1-i:]) % 2019)
    
ans = lst.count(0)
for i in set(lst):
    c = lst.count(i)
    ans += c*(c-1)//2
    
print(ans)    



### FIXED CODE ###

from collections import Counter

S = [int(i) for i in input()]
S.reverse()
lst = []
_sum = 0

for i in range(len(S)):
    _sum = (_sum + S[i] * pow(10,i,2019)) % 2019
    lst.append(_sum)
    
C = Counter(lst)    
ans = C[0]

for i in C:
    ans += C[i]*(C[i]-1)//2
print(ans)
### BUGGY CODE ###

n,m,q=map(int,input().split())
s=[[0 for i in range(n+1)] for j in range(n+1)]

a=list()

for i in range(m):
  l,r=map(int,input().split())
  s[l][r] += 1

for i in range(1,n+1):
  for j in range(1,n+1):
    s[i][j] += s[i][j-1] 

for i in range(q):
  l,r=map(int,input().split())
  t = 0
  for j in range(l,r+1):
    t += s[j][r]-s[j][l-1]
  a.append(t)

for i in range(q):
  print(a[i])


### FIXED CODE ###

n,m,q=map(int,input().split())
s=[[0 for i in range(n+1)] for j in range(n+1)]

a=list()

for i in range(m):
  l,r=map(int,input().split())
  s[l][r] += 1

for i in range(1,n+1):
  for j in range(1,n+1):
    s[i][j] += s[i][j-1] 

for i in range(1,n+1):
  for j in range(1,n+1):
    s[j][i] += s[j-1][i]

for i in range(q):
  l,r=map(int,input().split())
  t = s[r][r] - s[l-1][r] - s[r][l-1] + s[l-1][l-1]
  a.append(t)

for i in range(q):
  print(a[i])