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

from sys import stdin, gettrace
 
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()
 
def main():
  
  n,w=map(int,input().split())
  li=[]
  for i in range(n):
    temp=[int(x) for x in input().split()]
    li.append(temp)
  dp=[[[-1,-1] for j in range(w+1)] for i in range(n)]
  dp[n-1][0]=[li[n-1][1],li[n-1][1]]
  for i in range(n-1,-1,-1):
    for j in range(w,-1,-1):
      if j==0:
        dp[i][j]=li[i][1],li[i][1]
      if i==(n-1):
        if li[i][0]<=j:
          dp[i][j]=li[i][1],li[i][1]
        else:
          dp[i][j]=0,0
      else:
        mx=li[i][1]
        for k in range(i+1,n):
          if (j-li[i][0])>=li[k][0]:
            val=dp[k][j-li[i][0]]
            mx=max(mx,val[0]+li[i][1])
          val=dp[i+1][j]
          overall=max(mx,val[1])
          dp[i][j]=[mx,overall]
          
  print(dp[0][w][1])
 
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin, gettrace
import sys
sys.setrecursionlimit(1000000)
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()

def recursion(li,i,n,w,dp):
    if i==n or w==0:
        return 0
    if li[i][0]>w:
        if dp[i+1][w]==-1:
            x=recursion(li,i+1,n,w,dp)
            dp[i+1][w]=x            
        else:
            x=dp[i+1][w]
        return x
    else:
        if dp[i+1][w]==-1:
            x=recursion(li,i+1,n,w,dp)
            dp[i+1][w]=x            
        else:
            x=dp[i+1][w]
        if dp[i+1][w-li[i][0]]==-1:
            y=recursion(li,i+1,n,w-li[i][0],dp)
            dp[i+1][w-li[i][0]]=y
        else:
            y=dp[i+1][w-li[i][0]]            
        return max(li[i][1]+y,x)

def main():
    n,w=[int(x) for x in input().split()]
    li=[]
    for i in range(n):
        temp=[int(x) for x in input().split()]
        li.append(temp)
    dp=[[-1 for j in range(w+1)] for i in range(n+1)]
    print(recursion(li,0,n,w,dp))
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def main():
  d=[1]+[0]*12
  for c in input():
    d=[sum(d[(j-k)*9%13]for j in c<'?'and[int(c)]or range(10))%(10**9+7)for k in range(13)]
  print(d[5])
main()

### FIXED CODE ###

d=[1]+[0]*12
for i,c in enumerate(input()):
 p=[0]*13
 for j in range(13):
  for k in range(10):p[(j*10+k)%13]+=d[j]*(c>'9'or k==int(c))
 d=[t%(10**9+7)for t in p]
print(d[5])
### BUGGY CODE ###

def lensetlist(A):
    B = []
    for i in A:
        if i not in B:
            B.append(i)
    return len(B)

N, M = map(int, input().split())
A = []
B = []

for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
for i in range(M):
    A.append(B[i])
    B.append(A[i])

result = []
stack = []
ans = 0

def path(start, visited, count):
    count += 1
    if count > 10000:
        exit
    if len(visited) == N:
        result.append(visited[:])
        exit
    stack.append(start)
    while len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint in visited:
            continue
        visited.append(nextpoint)
        for i in range(2*M):
            if A[i] == start:
                path(B[i], visited, count)
        visited.pop()

path(1, [], 0)
print(lensetlist(result))


### FIXED CODE ###

N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(M)]

result = []
stack = []

def path(start, visited):
    if len(visited) >= N:
        result.append(visited[:])
        exit
    stack.append(start)
    if len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint not in visited:
            visited.append(nextpoint)
            for i in range(M):
                if A[i][0] == start:
                    path(A[i][1], visited)
                if A[i][1] == start:
                    path(A[i][0], visited)
            visited.pop()

path(1, [])
result = list(map(list, set(map(tuple, result))))
print(len(result))
### BUGGY CODE ###

N, M, K = map(int, input().split())
A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))

A_sum = [0]
B_sum = [0]

for a in A_list:
    A_sum.append(A_sum[-1] + a)

for b in B_list:
    B_sum.append(B_sum[-1] + b)

count = 0
for i, a in enumerate(A_sum):
    for j, b in enumerate(B_sum):
        if a + b <= K:
            if count < i + j:
                count = i + j
        else:
            break

print(count)

### FIXED CODE ###

N, M, K = map(int, input().split())
A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))

A_sum = [0]
B_sum = [0]

for a in A_list:
    A_sum.append(A_sum[-1] + a)

for b in B_list:
    B_sum.append(B_sum[-1] + b)

count = 0
j = M
for i, a in enumerate(A_sum):
    if a > K:
        break
    while B_sum[j] > K - a:
        j -= 1
    if count < i + j:
        count = i + j

print(count)
### BUGGY CODE ###


import collections

n = int(input())
a = list(map(int, input().split()))
c_lst = []
c = collections.Counter(a)
for i in c.most_common()[::-1]:
    if i[1] >= 2:
        c_lst.append(list(i))
if c_lst:
    values, counts = zip(*c_lst)
else:
    values = []

cnt = []
for i in range(len(c_lst)):
    cnt.append((c_lst[i][1] * (c_lst[i][1] - 1)) // 2)
cnt_ = sum(cnt)
    
for i in a:
    ans = 0
    if i in values:
        ans += ((c_lst[values.index(i)][1] - 1) * (c_lst[values.index(i)][1] - 2)) // 2
        ans += cnt_ - cnt[values.index(i)]
    else:
        ans = cnt_
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = [0] * n
for i in a:
    cnt[i-1] += 1
total = [0] * n
for i in range(n):
    total[i] = cnt[i] * (cnt[i] - 1) // 2
total_sum = sum(total)
for i in a:
    ans = total_sum
    ans -= total[i-1]
    ans += (cnt[i-1] - 1) * (cnt[i-1] - 2) // 2
    print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	# a_ext = {}
	b_sum_ext = {}
	b_ext = []
	# ai + aj = (j+1) - (i+1)
	# ai + i + 1 = -aj + j + 1

	for i, ai in enumerate(a):
		# a_ext[a[i] + i + 1] = 1
		log.print(a[i]+i+1, -a[i]+i+1)
		b_sum_ext[-a[i]+i+1] = b_sum_ext.get(-a[i]+i+1, 0)+1
	# log.print(b_sum_ext)
	for i in range(n):
		b_sum_ext[-a[i]+i+1] = b_sum_ext.get(-a[i]+i+1, 0)-1
		b_ext.append(dict(b_sum_ext))
	# log.print(b_ext)
	cnt = 0
	for i in range(n):
		for j in range(i, n):
			if a[i] + a[j] == j - i:
				log.print(i+1, j+1, a[i], a[j], b_ext[i].get(-a[j]+j+1, 0))
				cnt += 1
	log.print(cnt)
	cnt = 0
	for i, ai in enumerate(a):
		if b_ext[i].get(a[i] + i + 1, 0) != 0:
			log.print(i+1, a[i] + i + 1)
			cnt += b_ext[i].get(a[i] + i + 1, 0)
	print(cnt)

	


main()

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	# a_ext = {}
	b_sum_ext = {}
	b_ext = []
	# ai + aj = (j+1) - (i+1)
	# ai + i + 1 = -aj + j + 1

	for i, ai in enumerate(a):
		# a_ext[a[i] + i + 1] = 1
		log.print(a[i]+i+1, -a[i]+i+1)
		b_sum_ext[-a[i]+i+1] = b_sum_ext.get(-a[i]+i+1, 0)+1
	cnt = 0
	log.print(cnt)
	cnt = 0
	for i, ai in enumerate(a):
		b_sum_ext[-a[i]+i+1] = b_sum_ext.get(-a[i]+i+1, 0)-1
		if b_sum_ext.get(a[i] + i + 1, 0) != 0:
			log.print(i+1, a[i] + i + 1)
			cnt += b_sum_ext.get(a[i] + i + 1, 0)
	print(cnt)

	


main()
### BUGGY CODE ###

import bisect
N = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a = sorted(a)
b = sorted(b)
c = sorted(c)
z = [0] * N
ans = 0
for i in range(N):
  e = b[i]
  cin = insert_index = bisect.bisect_right(c,e)
  z[i] = N-cin
for i in range(N):
  d = a[i]
  bind = insert_index = bisect.bisect_right(b,d)
  ans += sum(z[bind:])
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a = sorted(a)
b = sorted(b)
c = sorted(c)
z = [0] * N
ans = 0
for i in range(N-1,-1,-1):
  e = b[i]
  cin =  bisect.bisect_right(c,e)
  if i + 1 == N:
    z[i] = N-cin
  else:
    z[i] = z[i+1] + N-cin
for i in range(N):
  d = a[i]
  bind =  bisect.bisect_right(b,d)
  if bind == N:
    continue
  ans += z[bind]
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

for _ in range(m):
    l, r, d = [int(x) for x in input().split()]
    l -= 1
    r -= 1
    g[l].append((r, d))
    g[r].append((l, -d))

visited = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    d = [0] * n
    stack = [i]
    while stack:
        u = stack.pop()
        visited[u] = 1
        for v, d_ in g[u]:
            if d[v] == 0 and v != i:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
print("Yes")


### FIXED CODE ###

n, m = map(int, input().split())
ed = [[] for _ in range(n)]  # グラフ
v = [None] * n
for _ in range(m):
  l, r, d = map(int, input().split())
  ed[l-1].append((r-1, d))  # l -> r
  ed[r-1].append((l-1, -d))  # r -> l

visited = [False] * n  # 訪問フラグ（非連結の可能性の為）

def dfs(start):
  s = [start]
  v[start] = 0
  while s:
    label = s.pop()
    if visited[label] == False:
      visited[label] = True
      for to, dist in ed[label]:
        if v[to] is None:
          v[to] = v[label] + dist
          s.append(to)
        else:
          if v[to] != v[label] + dist:
            return False
  return True

is_exist = True
for i in range(n):
  if v[i] is None:
    if not dfs(i):
      print('No')
      is_exist = False
      break
if is_exist:
  print("Yes")
### BUGGY CODE ###


if __name__ == '__main__':

    Q, H, S, D = map(int, input().split())
    N = int(input())

    #各サイズの量
    amounts = {'Q' : 0.25, 'H' : 0.5, 'D' : 1.0, 'D' : 2.0}
    #1リットルあたりの値段
    sizes = {'Q' : int(Q * 4.0), 'H' : int(H * 2.0), 'S' : S, 'D' : int(D * 0.5)}
    sizes = sorted(sizes.items(), key=lambda x: x[1])
    sum_price = 0

    while N > 0:
        for size in sizes:

            if size[0] != 'D':
                if N - 1 >= 0:
                    N -= 1
                    sum_price += size[1]
                else:
                    break
            else:
                if N - 2 >= 0:
                    N -= 2
                    sum_price += D
                else: break
    print(sum_price)


### FIXED CODE ###

if __name__ == '__main__':
    Q, H, S, D = map(int, input().split())
    N = int(input())
    #各サイズの量
    #amounts = {'Q' : 0.25, 'H' : 0.5, 'D' : 1.0, 'D' : 2.0}
    #1リットルあたりの値段
    sizes = {'Q' : int(Q * 4.0), 'H' : int(H * 2.0), 'S' : S, 'D' : int(D * 0.5)}
    sizes = sorted(sizes.items(), key=lambda x: x[1])
    sum_price = 0
    while N > 0:
        for size in sizes:
            if size[0] != 'D':
                sum_price += size[1] * N
                N = 0
            else:
                num = int(N / 2)
                N -= 2 * num
                sum_price += D * num
    print(sum_price)
### BUGGY CODE ###

N= int(input())
A = list(map(int,input().split()))
B= [A.count(i+1) for i in range(N)]
for i in range(N):
  print(B[i])
          

### FIXED CODE ###

N= int(input())
A = list(map(int,input().split()))
B =[0 for i in range(N)]
for i in A:
  B[i-1] += 1
for i in B:
  print(i)
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(a,b+1):
    if((i-a)<k or (b-i)<k):print(i)

### FIXED CODE ###

a,b,k=map(int,input().split())
for i in range(a,min(b+1,a+k)):
    print(i)
if(a+k<b-k+1):
    for i in range(b-k+1,b+1):print(i)
else:
    for i in range(a+k,b+1):print(i)
### BUGGY CODE ###

s=input()


i=0
c=0
flag=0
while True:
	if i>len(s)-3: break
	if s[i]=="A" and s[i+1]=="B" and s[i+2]=="C":
		s=s[:i]+"B"+s[i+1:]
		s=s[:i+1]+"C"+s[i+2:]
		s=s[:i+2]+"A"+s[i+3:]
		c+=1
		if i>0:
			i-=1
			flag+=1
		continue
	else:
		if flag:
			i+=2+flag
			flag=0
		else: i+=1

print(c)

### FIXED CODE ###

s=input()


i=0
c=0
flag=0
while True:
	if i>len(s)-2: break
	if s[i]=="A":
		flag+=1
		i+=1
	elif flag and s[i:i+2]=="BC":
		c+=flag
		i+=2
	else:
		flag=0
		i+=1

print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def lcm(a, b):
    return (a // gcd(a, b)) * b

a_lcm = 1
for v in a:
    a_lcm = lcm(a_lcm, v)

ans = 0
for v in a:
    ans = (ans + (a_lcm // v)) % MOD

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

import collections

lcm_pf = collections.defaultdict(int)
for i, v in enumerate(a):
    j = 2
    pf = {}
    while j ** 2 <= v:
        ext = 0
        while v % j == 0:
            ext += 1
            v //= j
        if ext:
            pf[j] = ext
            lcm_pf[j] = max(lcm_pf[j], ext)
        j += 1
    if v != 1:
        pf[v] = 1
        lcm_pf[v] = max(lcm_pf[v], 1)

lcm = 1
for p in lcm_pf:
    lcm = lcm * (p ** lcm_pf[p])

ans = 0
for v in a:
    ans = ans + (lcm // v)
print(ans % MOD)
### BUGGY CODE ###

import itertools

N, x = map(int, input().split())
a = list(map(int, input().split()))

if sum(a) == x:
    print(N)
    exit()

for i in range(N - 1, 0, -1):
    for element in itertools.combinations(a, i):
        if sum(element) <= x:
            print(i)
            exit()

print(0)
exit()


### FIXED CODE ###

N, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

if sum(a) == x:
    print(N)
    exit()

low = 0
high = N - 1
most_happy = 0

while low <= high:
    i = int((low + high) / 2)
    if sum(a[0:i]) <= x:
        low = i + 1
        if i > most_happy:
            most_happy = i
    else:
        high = i - 1

print(most_happy)
exit()
### BUGGY CODE ###

mod = int(1e9 + 7)
N = int(input())
A = list(map(int, input().split()))
S = 0
j = 0
while A != [0 for i in range(N)]:
  m = 0
  n = 0
  for i in range(N):
    if A[i] % 2 == 1:
      m += 1
    else:
      n += 1
    A[i] //= 2
  S += (((m * n) * (2 ** j)) % mod)
  j += 1
S %= mod
print(S)

### FIXED CODE ###

mod = int(1e9 + 7)
N = int(input())
A = [format(i, '060b') for i in map(int, input().split())]
S = 0
for k in range(60):
  s = [b[59-k] for b in A]
  v = s.count('0')*s.count('1')
  S += (v<<k)
S %= mod
print(S)
### BUGGY CODE ###

N,K = [ int(it) for it in input().split() ]
S = [ int(it) for it in input() ]

li = []

v = 1
c = 0
for it in S:
  if (v != it ):
    li.append(c)
    c=1
  else:
    c+=1
  v = it
li.append(c)
s = 0
lis = [0]*(len(li)+1)
for i in range(len(li)):
  lis[i+1]=lis[i]+li[i]
s = 0
for i in range(N):
  if (i*2>=N):
    continue
  ds = sum( li[i*2:i*2+2*K+1] )
  a = min(i*2,len(li))
  b = min(i*2+2*K+1,len(li))

  ds2 = lis[b]-lis[a]
  s = max(s,ds)
print (s)

### FIXED CODE ###

N,K = [ int(it) for it in input().split() ]
S = [ int(it) for it in input() ]

li = []

v = 1
c = 0
for it in S:
  if (v != it ):
    li.append(c)
    c=1
  else:
    c+=1
  v = it
li.append(c)
s = 0
lis = [0]*(len(li)+1)
for i in range(len(li)):
  lis[i+1]=lis[i]+li[i]
s = 0
for i in range(N):
  if (i*2>=N):
    continue
  a = min(i*2,len(li))
  b = min(i*2+2*K+1,len(li))

  ds2 = lis[b]-lis[a]
  s = max(s,ds2)
print (s)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=a[0]
for i in a[1:]:
    ans*=i
print(-1 if ans>10**18 else ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
ans=0
if a[0]==0:
    print(0)
else:
    a=a[::-1]
    ans=a[0]
    for i in a[1:]:
        ans*=i
        if ans>10**18:
            print(-1)
            break
    else:
        print(ans)
### BUGGY CODE ###

def MAIN():
    H, W = map(int, input().split())
    MAP = tuple(input() for _ in range(H))
    R, C = map(int, input().split())
    PTN = tuple(input() for _ in range(R))
    def solve(a, b):
        k = 0
        for i in range(a, a + R):
            if MAP[i][b:b + C] == PTN[k]:
                k += 1
            else:
                return False
        return True
    for i in range(H - R + 1):
        for j in range(W - C + 1):
            if solve(i, j):
                print(i, j)
MAIN()



### FIXED CODE ###

base1 = 1009
base2 = 1013
mask = (1 << 32) - 1
def calc_hash(f, r, c):
    global ph, pw, h
    tmp = [[0] * c for _ in range(r)]
    dr, dc = r - ph, c - pw
    # t1 = 1
    t1 = (base1 ** pw) & mask
    # for _ in range(pw):
        # t1 = (t1 * base1) & mask
    for i in range(r):
        e = 0
        for j in range(pw):
            e = e * base1 + f[i][j]
        for j in range(dc):
            tmp[i][j] = e
            e = (e * base1 - t1 * f[i][j] + f[i][j + pw]) & mask
        tmp[i][dc] = e
    t2 = 1
    for _ in range(ph):
        t2 = (t2 * base2) & mask
    for j in range(dc + 1):
        e = 0
        for i in range(ph):
            e = e * base2 + tmp[i][j]
        for i in range(dr):
            h[i][j] = e
            e = (e * base2 - t2 * tmp[i][j] + tmp[i + ph][j]) & mask
        h[dr][j] = e
th, tw = map(int, input().split())
t = tuple(tuple(ord(c) for c in input()) for _ in range(th))
ph, pw = map(int, input().split())
p = tuple(tuple(ord(c) for c in input()) for _ in range(ph))
ans = []
if th >= ph and tw >= pw:
    h = [[0] * tw for _ in range(th)]
    calc_hash(p, ph, pw)
    key = h[0][0] & mask
    calc_hash(t, th, tw)
    for i in range(th - ph + 1):
        for j in range(tw - pw + 1):
            if h[i][j] & mask == key:
                ans.append(f"{i} {j}")
if ans:
    print("\n".join(a for a in ans))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M = list(map(int,input().split()))
A = sorted(list(map(int,input().split())))
Amin = min(A)
tmp = sorted([list(map(int,input().split())) for i in range(M)],key = lambda x:-x[1])

cnt = 0
t = []
for a,b in tmp:
    t=t+[b]*a
    cnt+= a
    if cnt >=N:
        break
    if cnt<N and b <= A[cnt-1]:
        break
A = A + t
A.sort(reverse = 1)
print(sum(A[:N]))

### FIXED CODE ###

import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for _ in range(M)],key = lambda x:-x[1])

    t = []
    for a,b in tmp:
        t+=[b]*a
        
        if len(t) >=N:
            break

    A += t
    A.sort(reverse = 1)
    print(sum(A[:N]))

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

N = int(input())
A = [int(i) for i in input().split()]

s = [0]
sum = 0
for i in range(N):
    sum += A[i]
    s.append(sum)
s = sorted(s)

ans = 0
for r in set(s):
    if s.count(r) >= 2:
        ans += (s.count(r)*(s.count(r)-1))//2

print(ans)


### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = [int(i) for i in input().split()]

d = defaultdict(int)

d[0] = 1
sum = 0
for i in range(N):
    sum += A[i]
    d[sum] += 1

ans = 0
for v in d.values():
    if v >= 2:
        ans += (v*(v-1))//2

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

# for loop
n = int(raw_input())
ls = []
for i in range(n):
    ls.append(int(raw_input()))

ans = None
for k in range(n):
    for j in range(k+1,n):
        dif = ls[j]-ls[k]
        if ans is None:
            ans = dif
        elif ans < dif:
            ans = dif
print ans

### FIXED CODE ###

n = int(raw_input())
R = []
R.append(int(raw_input()))
minv = R[0]
maxv = -1 * 10**9
for j in xrange(1,n):
    R.append(int(raw_input()))
    maxv = max(maxv,R[j]-minv)
    minv = min(minv,R[j])
print maxv
### BUGGY CODE ###

Q = int(input())
lr = []
for i in range(Q):
   lr.append(list(map(int, input().split())))

N = 100000
like_number = [3]
prime_number = [2]
for i in range(3, N, 2):
   flag = 0
   for j in range(3, int(i**0.5)+1, 2):
      if i%j == 0:
         flag = 1
         break
   if flag == 0:
      prime_number.append(i)
      if ((i+1)/2)%2 == 1:
         if (i+1)/2 in prime_number:
            like_number.append(i)
         

for i in range(Q):
   count = 0
   for j in range(lr[i][0], lr[i][1]+1):
      if j in like_number:
         count = count + 1
   print(count)


### FIXED CODE ###

def main():
    Q = int(input())
    L = [0 for _ in range(Q)]
    R = [0 for _ in range(Q)]
    for i in range(Q):
        L[i], R[i] = map(int, input().split())

    N = 100000
    sosu = [1 for _ in range(N)]
    sosu[0] = 0
    for i in range(1,int(N**0.5)):
        k = i+1
        if sosu[i] == 1:
            j = k + k
            while j <= N:
                sosu[j-1] = 0
                j = j+k
    like = [0 for _ in range(N)]
    for i in range(2, N, 2):
        if sosu[i]==1 and sosu[(i+2)//2-1]==1:
            like[i] = 1
    like_wa = [0 for _ in range(N+1)]
    for i in range(N):
        like_wa[i+1] = like_wa[i] + like[i]

    for i in range(Q):
        print(like_wa[R[i]] - like_wa[L[i]-1])

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

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mini = min(A[0:L])
ans.append(mini)
if N > 10 ** 6 : print(1)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])