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

n, w = map(int, input().split())
W = [0 for i in range(n)]
V = [0 for i in range(n)]
for i in range(n):
    W[i], V[i] = map(int, input().split())

DP = [[0 for j in range(w + 1)] for i in range(n)]
for j in range(W[0], w + 1):
    DP[0][j] = V[0]

for i in range(1, n):
    for j in range(w + 1):
        if j - W[i] >= 0:
            DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i])
        else:
            DP[i][j] = DP[i - 1][j]

print(DP[n - 1][w])

### FIXED CODE ###

n, w = map(int, input().split())
W = [0 for i in range(n)]
V = [0 for i in range(n)]
for i in range(n):
    W[i], V[i] = map(int, input().split())

DP = [[0 for j in range(w + 1)] for i in range(n)]
for j in range(W[0], w + 1):
    DP[0][j] = V[0]

for i in range(1, n):
    for j in range(w + 1):
        if j - W[i] >= 0:
            DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i])
        else:
            DP[i][j] = DP[i - 1][j]

print(DP[n - 1][w])
### BUGGY CODE ###

X = int(input())

b = 0
while 1:
    a = (X + b ** 5) ** (1/5)
    if a.is_integer() == True:
        break
    b = -b
    c = X + b ** 5
    if c >= 0:
        a = c ** (1/5)
        if a.is_integer() == True:
            break
    b = -b
    b += 1
print(int(a), b)

### FIXED CODE ###

import sys

X = int(input())
for i in range(-118, 120):
    for j in range(-119, 119):
        if i ** 5 - j ** 5 == X:
            print(i, j)
            sys.exit(0)
### BUGGY CODE ###

S = input()
s_rev = S[::-1]

r_list = [0] * 2019
r_list[0] = 1
num = 0
for i in range(len(S)):
    num += (10**i)*int(s_rev[i])
    num %= 2019
    r_list[num] += 1

ans = 0
for i in range(2019):
        ans += r_list[i]*(r_list[i]-1)//2

print(ans)


### FIXED CODE ###

S = input()
s_rev = S[::-1]

r_list = [0] * 2019
r_list[0] = 1
num, d = 0, 1
for i in range(len(S)):
    num += d*int(s_rev[i])
    num %= 2019
    r_list[num] += 1
    d *= 10
    d %= 2019

ans = 0
for i in range(2019):
        ans += r_list[i]*(r_list[i]-1)//2

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

H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
A = [[[0,0] for _ in range(W)] for _ in range(H)]
for i in range(H):
    cur = 0
    cnt = 0
    for j in range(W):
        if S[i][j]=="#":
            A[i][j-1][0] = cnt
            cur = j+1
            cnt = 0
        else:
            cnt += 1
        A[i][W-1][0] = cnt
for i in range(H):
    for j in range(W-1,-1,-1):
        if A[i][j][0]>0:
            cnt = A[i][j][0]
        elif S[i][j]!="#":
            A[i][j][0] = cnt
        else:
            cnt = 0
for j in range(W):
    cur = 0
    cnt = 0
    for i in range(H):
        if S[i][j]=="#":
            A[i-1][j][1] = cnt
            cur = i+1
            cnt = 0
        else:
            cnt += 1
    A[H-1][j][1] = cnt
for j in range(W):
    for i in range(H-1,-1,-1):
        if A[i][j][1]>0:
            cnt = A[i][j][1]
        elif S[i][j]!="#":
            A[i][j][1] = cnt
        else:
            cnt = 0
cmax = 0
for i in range(H):
    for j in range(W):
        cmax = max(cmax,sum(A[i][j]))
print(cmax-1)

### FIXED CODE ###

H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
L = [[0 for _ in range(W)] for _ in range(H)]
R = [[0 for _ in range(W)] for _ in range(H)]
U = [[0 for _ in range(W)] for _ in range(H)]
D = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if j==0 and S[i][j]==".":
            L[i][j] = 1
        elif j>0 and S[i][j]==".":
            L[i][j] = L[i][j-1]+1
        if i==0 and S[i][j]==".":
            U[i][j] = 1
        elif i>0 and S[i][j]==".":
            U[i][j] = U[i-1][j]+1
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if j==W-1 and S[i][j]==".":
            R[i][j] = 1
        elif j<W-1 and S[i][j]==".":
            R[i][j] = R[i][j+1]+1
        if i==H-1 and S[i][j]==".":
            D[i][j] = 1
        elif i>0 and S[i][j]==".":
            D[i][j] = D[i+1][j]+1
cmax = 0
for i in range(H):
    for j in range(W):
        cmax = max(cmax,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
print(cmax)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for l in range(n):
  for r in range(l, n):
    if sum(a[l:r+1]) % m == 0:
      ans += 1
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a_t = [0]
for i in range(n):
    a_t.append(a[i] + a_t[i])
dict = {}
for i in range(n + 1):
    b = a_t[i] % m
    if b in dict:
        dict[b] += 1
    else:
        dict[b] = 1
ans = 0
for i in dict.values():
    ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

N=int(input())
P=[]
ans=0
for i in range(N):
  P.append(i+1)
print(sum(P) - N)

### FIXED CODE ###

N=int(input())
print((N+1) * (N // 2) - N if N%2==0 else (N+1) * (N // 2) + int(N/2+1) - N)
### BUGGY CODE ###

T = int(input())
ABCD = [ list(map(int,input().split())) for _ in range(T)]

def check(a,b,c,d):
    if b > d or a < b:
        print("No")
        return
    elif c >= b:
        print("Yes")
        return
    def_a = a % b
    a = def_a
    while True:
        a = (a + d) % b
        if a > c:
            print("No")
            return
        elif def_a == a:
            print("Yes")
            return

for abcd in ABCD:
    check(abcd[0],abcd[1],abcd[2],abcd[3])


### FIXED CODE ###

T = int(input())
ABCD = [ list(map(int,input().split())) for _ in range(T)]
import fractions

def check(a,b,c,d):
    if b > d or a < b:
        print("No")
        return
    elif c >= b:
        print("Yes")
        return
    def_a = a % b
    a = def_a
    while True:
        a = (a + d) % b
        if a > c:
            print("No")
            return
        g = fractions.gcd(b,d)
        f = (b -a) // g
        if (b - a) % g == 0:
            f -= 1
        if g == 0 or c >= a + f * g:
            print("Yes")
            return
        print("No")
        return

for abcd in ABCD:
    check(abcd[0],abcd[1],abcd[2],abcd[3])
### BUGGY CODE ###

import numpy
k=int(input())
d=0
for a in range(1,k+1) :
    for b in range(1,k+1):
        x=numpy.gcd(a,b)
        for c in range(1,k+1):
            d+=numpy.gcd(x,c)
print(d)

### FIXED CODE ###

import math
d=0
k=int(input())
for a in range(1,k+1) :
    for b in range(1,k+1):
        x=math.gcd(a,b)
        for c in range(1,k+1):
            d+=math.gcd(x,c)
print(d)
### BUGGY CODE ###

def main(n,k,h):
    #初期化
    inf = 2**31 -1
    dp = [inf] * n
    dp[0] = 0
    #現在の足場
    for i in range(n):
        #ジャンプする距離
        for j in range(1, k+1):
            #ジャンプ先が範囲外ならスキップ
            if n-1 < i+j:
                break
            #dpマップに値を配る
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j] - h[i]))
    return dp[-1]

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

### FIXED CODE ###

def main2(N,h,K):
    dp = [0] * N
    for i in range(1,N):
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(max(0, i-K), i)])
    return dp[-1]

N, K = map(int, input().split())
h = list(map(int, input().split()))
print(main2(N,h,K))
### BUGGY CODE ###

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)
        self.connected_num = [1] * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank
        connected_num = self.connected_num
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                UFdata[x] = UFdata[y]
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            connected_num[x] += connected_num[y]
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
MAP= [ [0] * (N+1) for _ in range(N+1)]
import sys
input = sys.stdin.readline
PQ = [ [int(j) for j in input().split()] for _ in range(K)]
RS = [ [int(j) for j in input().split()] for _ in range(L)]

for i in range(K):
    p,q = PQ[i]
    UF1.unite(p,q)
for i in range(L):
    p,q = RS[i]
    UF2.unite(p, q)
counter=[]
for i in range(1,N+1):
  counter.append((UF1.find(i),UF2.find(i)))
from collections import Counter  
p=Counter(counter)

ans = [0]*(N+1)
for i in range(1,N+1):
    ans[i] = p[(UF1.find(i),UF2.find(i))]

del ans[0]
# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))


### FIXED CODE ###

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank 
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
# MAP= [ [0] * (N+1) for _ in range(N+1)]
import sys
input = sys.stdin.readline
#PQ = [ [int(j) for j in input().split()] for _ in range(K)]
#RS = [ [int(j) for j in input().split()] for _ in range(L)]

for i in range(K):
    p,q = map(int,input().split())
    UF1.unite(p,q)
for i in range(L):
    p,q = map(int,input().split())#RS[i]
    UF2.unite(p, q)
counter=[]
from collections import defaultdict
cntdic =defaultdict(int)
for i in range(1,N+1):
  counter.append(UF1.find(i)+UF2.find(i)*10**6)
  cntdic[counter[-1]]+=1 

ans = [0]*(N+1)
for i in range(1,N+1):
    ans[i] = cntdic[counter[i-1]]

del ans[0]
# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))
### BUGGY CODE ###

n=int(input())
a= list(map(int, input().split())) 
#a.sort()
#print(a)
#print(sum(a[:-1])+a[-1]//2)
b=sorted(a)
for i in range(len(a)):
  print(a.index(b[i])+1,end=" ")

### FIXED CODE ###

a=int(input())
b=[0]*a
c=list(map(int,input().split()))

for i in range(a):
  b[c[i]-1]+=i+1
print(' '.join(map(str, b)))
### BUGGY CODE ###

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

res = 1
i = 1

while i ** N <= P:
    if P % i ** N == 0:
        res = i

    i += 1

print(res)


### FIXED CODE ###

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

if N == 1:
    print(P)
    exit()

div = 2
res = 1
R = P

while div * div <= R and div <= P:
    cnt = 0
    while P % div == 0:
        P /= div
        cnt += 1

        if cnt == N:
            res *= div
            cnt = 0
    div += 1

print(res)
### BUGGY CODE ###

import sys
from collections import defaultdict


def main():
    N = int(input())
    P = tuple(map(int, input().split()))

    Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

    Sitting = [1] * (N * N)
    Kcount = 0


    def Kcheck(qsn, cdsn):
        if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
            Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
            queue.append(cdsn)


    for sn in P:
        csn = sn - 1
        Kcount += Kcost[csn]
        Sitting[csn] = 0
        queue = [csn]
        checked = defaultdict(lambda: 0)

        while queue:
            qsn = queue.pop()

            if checked[qsn]: continue

            checked[qsn] = 1
            div, mod = divmod(qsn, N)
            if mod: Kcheck(qsn, qsn - 1)
            if mod != N - 1: Kcheck(qsn, qsn + 1)
            if div: Kcheck(qsn, qsn - N)
            if div != N - 1: Kcheck(qsn, qsn + N)

    print(Kcount)


if __name__ == '__main__':
    main()

sys.exit()


### FIXED CODE ###

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

Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

Sitting = [1] * (N * N)
Kcount = 0


def Kcheck(qsn, cdsn):
    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
        queue.append(cdsn)


for sn in P:
    csn = sn - 1
    Kcount += Kcost[csn]
    Sitting[csn] = 0
    queue = [csn]

    while queue:
        qsn = queue.pop()
        div, mod = divmod(qsn, N)
        if mod: Kcheck(qsn, qsn - 1)
        if mod != N - 1: Kcheck(qsn, qsn + 1)
        if div: Kcheck(qsn, qsn - N)
        if div != N - 1: Kcheck(qsn, qsn + N)

print(Kcount)
### BUGGY CODE ###

n,m=map(int,input().split())
ans=0

if m%n==0:
    ans=m//n
else:
    for i in range(1,m//n +1)[::-1]:
        if m%i == 0:
            ans = i
            break
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
m_root=int(m**0.5)
div_l=[]
ans=0

for i in range(1,m_root + 1):
    if m%i == 0:
        div_l.append(i)
        div_l.append(m//i)

if m//n in div_l:
    ans = m//n
else:
    div_l.append(m//n)
    div_l.sort()
    ans = div_l[div_l.index(m//n) - 1]
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
N,M = (int(x) for x in input().split())
a = set(int(input()) for _ in range(M))
mem = [0] * N
def count_steps(n):
    if mem[n-1]:
        return mem[n-1]
    elif n == 1:
        if 1 in a:
            return 0
        else:
            mem[0] = 1
            return 1
    elif n == 2:
        if 1 in a:
            mem[1] = 1
            return 1
        else:
            mem[1] = 2
            return 2
    elif n - 1 in a and n - 2 in a:
        return 0
    elif n - 1 in a:
        mem[n-1] = count_steps(n-2)
        return mem[n-1]
    elif n - 2 in a:
        mem[n-1] = count_steps(n-1)
        return mem[n-1]
    else:
        mem[n-1] = (count_steps(n-1) + count_steps(n-2)) % 1000000007
        return mem[n-1]
print(count_steps(N))

### FIXED CODE ###

N,M = (int(x) for x in input().split())
a = set(int(input()) for _ in range(M))
dp = [0] * N
broke = False
if N == 1:
    print('1')
    broke = True
elif 1 in a and 2 not in a:
    dp[1] = 1
elif 1 not in a and 2 in a:
    dp[0] = 1
else:
    dp[0] = 1
    dp[1] = 2
if 1 in a and 2 in a:
    print('0')
    broke = True
else:
    for i in range(3,N+1):
        if i-1 in a and i-2 in a:
            print('0')
            broke = True
            break
        elif i-1 in a:
            dp[i-1] = dp[i-3]
        elif i-2 in a:
            dp[i-1] = dp[i-2]
        else:
            dp[i-1] = (dp[i-2] + dp[i-3]) % 1000000007
if broke == False:
    print(dp[N-1])
### BUGGY CODE ###

# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(N, s):
    MOD = int(1e9 + 7)
    dp = [[0] * N for _ in range(N)]
    for j in range(N):
        dp[0][j] = 1
    for i in range(1, N):
        # csum: Cumulative sum
        # csum[x] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][x]
        csum = list(accum(dp[i - 1], lambda x, y: (x + y) % MOD))
        for j in range(N - i):  # N-(i+1)+1 = N-i
            if s[i - 1] == "<":
                dp[i][j] = (dp[i][j] + csum[N - i] - csum[j]) % MOD
            else: #s[i-1] == ">"
                dp[i][j] = (dp[i][j] + csum[j]) % MOD
    return(dp[-1][0])


N = int(input()) # 2 <= N <= 30000
s = input().rstrip() # len(s) = N - 1

print(f(N, s))


### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

def f2(N, s):
    MOD = int(1e9 + 7)
    dp = [1] * N
    for i in range(1, N):
        csum = list(dp)
        for j in range(1, N - i + 1):
            csum[j] += csum[j - 1]
        csum_ = csum[N - i]
        i_ = i - 1
        for j in range(N - i):  # N-(i+1)+1 = N-i
            dp[j] = csum[j] if s[i_] == ">" else (csum_ - csum[j] + MOD) % MOD
    return(dp[0])

N = int(input()) # 2 <= N <= 30000
s = input().rstrip() # len(s) = N - 1
print(f2(N, s))
### BUGGY CODE ###

from copy import deepcopy
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]

state = []
# 初期状態
for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            state.append([w, h])

tmp = []
ret = 0
while len(state) > 0:
    tmp = list()
    ret += 1
    for x, y in state:
        for nx, ny in ((1,0), (-1,0), (0,1), (0,-1)):
            nx += x
            ny += y
            if nx < 0 or ny < 0 or nx >= W or ny >= H:
                continue

            if field[ny][nx] == ".":
                field[ny][nx] = "#"
                tmp.append([nx, ny])
    state = tmp
    


print(ret-1)

### FIXED CODE ###

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]

state = []
# 初期状態
for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            state.append([w, h])

tmp = []
ret = 0
while len(state) > 0:
    tmp = list()
    ret += 1
    for x, y in state:
        for nx, ny in ((1,0), (-1,0), (0,1), (0,-1)):
            nx += x
            ny += y
            if nx < 0 or ny < 0 or nx >= W or ny >= H:
                continue

            if field[ny][nx] == ".":
                field[ny][nx] = "#"
                tmp.append([nx, ny])
    state = tmp

print(ret-1)
### BUGGY CODE ###

def actual(K, S):
    my_range = lambda n: range(n + 1)

    count = 0

    for x in my_range(K):
        for y in my_range(K):
            for z in my_range(K):
                if x + y + z == S:
                    count += 1

    return count
  
K, S = map(int, input().split())

print(actual(K, S))

### FIXED CODE ###

def actual(K, S):
    my_range = lambda n: range(n + 1)

    count = 0

    for x in my_range(K):
        for y in my_range(K):
            z = S - (x + y)
            if 0 <= z <= K:
                count += 1
    return count

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

print(actual(K, S))
### BUGGY CODE ###

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

Aball = ""
for i in range(a):
    Aball+="b"
Bball = ""
for i in range(b):
    Bball+="a"

t = ""
while len(t) <= n:
    t+=Aball
    if len(t)>n:
        t = t[:n]
        break
    t+=Bball
    if len(t)>n:
        t = t[:n]
        break
count = t.count("b")
print(count)


### FIXED CODE ###

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

count = a*(n//(a+b))

add = n%(a+b)
if add < a:
    count+=add
else:
    count+=a
print(count)
### BUGGY CODE ###

k, s = map(int, input().split())
ans = 0
for x in range(k + 1):
  for y in range(k + 1):
    for z in range(k + 1):
      if x + y + z == s:
        ans += 1
print(ans)

### FIXED CODE ###

k, s = map(int, input().split())
ans = 0
for x in range(k + 1):
  for y in range(k + 1):
      if s - x - y <= k and s - x - y >= 0:
        ans += 1
print(ans)
### BUGGY CODE ###

def solve(n,k,ar):

    dp = [int(1e16)]*n
    dp[0] = 0

    for i in range(n):
        for j in range(i+1,i+k+1):
            if j < n:
                dp[j] = min(dp[j], dp[i] + abs(ar[i]-ar[j]))
    print(dp[n-1])

def solve1(n,k,ar):
    dp = [int(1e9)] * (n)
    dp[0] = 0
    for i in range(1,n):
        for k in range(1,k+1):
            if i-k >= 0:
                dp[i] = min(dp[i], dp[i-k] + abs(ar[i]-ar[i-k]))

    print(dp[n-1])


if __name__ == '__main__':
    n,k = map(int,input().split())
    ar = list(map(int,input().split()))

    solve(n,k,ar)

### FIXED CODE ###

import sys

def solve(n,k,ar):

    dp = [sys.maxsize]*n
    dp[0] = 0

    for i in range(n):
        for k in range(1,k+1):
            if i+k <= n-1:
                dp[i+k] = min(dp[i+k], dp[i] + abs(ar[i]-ar[i+k]))

    print(dp[n-1])



if __name__ == '__main__':
    n,k = map(int,input().split())
    ar = list(map(int,input().split()))

    solve(n,k,ar)
### BUGGY CODE ###

n=int(input())
s=input()
a=[]
for i in s:
    if i=='W': a.append(1)
    else: a.append(-1)
a2=[-1*i for i in a]
suma=[sum(a[i+1:]) for i in range(len(a))]
suma2=[sum(a2[:i]) for i in range(len(a))]
#print(a,a2)
count=0
for i in range(len(a)):
    d=suma[i]+suma2[i]
    if count<d:count=d
    #print(sum(a[i+1:]),sum(a2[:i]),d)
print((n-1-count)//2)

### FIXED CODE ###

n=int(input())
s=input()
a=[]
for i in s:
    if i=='W': a.append(1)
    else: a.append(-1)
a2=[-1*i for i in a]
suma=[sum(a)-a[0]]
for i in range(len(a)-1):
    suma.append(-a[i+1]+suma[i])
suma2=[0]
for i in range(len(a2)-1):
    suma2.append(suma2[i]+a2[i])
#print(a,a2)
count=0
for i in range(len(a)):
    d=suma[i]+suma2[i]
    if count<d:count=d
    #print(sum(a[i+1:]),sum(a2[:i]),d)
print((n-1-count)//2)
### BUGGY CODE ###

n,k = map(int,input().split())
ans = 0
for i in range(n):
    if i < k:
      c = i
      d=0
      while c<k:
        c = c*2
        d+=1
      ans -=float((2**d-1)/(n*(2**d)))
print(ans)


### FIXED CODE ###

n,k = map(int,input().split())
ans = 1
for i in range(1,n+1):
    if i < k:
      c = i
      d=0
      while c<k:
        c = c*2
        d+=1
      ans -=float((2**d-1)/(n*(2**d)))
print(ans)
### BUGGY CODE ###


def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    if n%2 == 0:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            return False
    return True

Q = int(input())
for i in range(Q):
    cnt = 0
    l,r = map(int,input().split())
    for j in range(l,r+1):
        if j == 2 :
            continue
        if is_prime(j) :
            if is_prime((j+1)/2):
#                print(j,(j+1)/2,"is like number.")
                cnt += 1
    print(cnt)

### FIXED CODE ###

def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    if n%2 == 0:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            return False
    return True

def is_like_num(n):
    return is_prime(n) and is_prime((n+1)//2)

erast_list =[0]*100001
cnt = 0
for i in range(100001):
    if is_like_num(i):
        cnt+=1
    erast_list[i] = cnt
# print(erast_list[:5])
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
#    print(erast_list[R+1],erast_list[L-1])
    print(erast_list[R+1]-erast_list[L-1])
### BUGGY CODE ###

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

T=[]
for m in range(M):
    t=[BC[m][1]]*BC[m][0]
    T=T+t

D=A+T
D=sorted(D,reverse=True)

ANS=sum(D[:N])

print(ANS)

    


### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[list(map(int,input().split())) for i in range(M)]
BC=sorted(BC,key=lambda x:x[1],reverse=True)

T=[0]*N
count=0
cntmp=0
for m in range(M):
    count+=BC[m][0]
    if count>N:
        T[cntmp:]=[BC[m][1]]*(N-count+BC[m][0])
        break
    else:
        T[cntmp:count]=[BC[m][1]]*BC[m][0]
    cntmp=count


#print(A)
#print(T)

D=A+T
D=sorted(D,reverse=True)

ANS=sum(D[:N])

print(ANS)
### BUGGY CODE ###

import heapq
n,q=map(int,input().split())

event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append([s-x,1,x])
    event.append([t-x,-1,x])

for i in range(q):
    event.append([int(input()),2,i])
event.sort()

ans=[0]*q

stop=set()
hq=[]
for e in event:
    t,op,x=map(lambda x:x,e)
    if op==1:
        heapq.heappush(hq,x)
        stop.add(x)
    elif op==-1:
        stop.remove(x)

    else:
        while hq and hq[0] not in stop:
            heapq.heappop(hq) 
        ans[x]=hq[0] if hq else -1
    
for x in ans:
    print(x)

### FIXED CODE ###

def main():
    from heapq import heappush, heappop
    import sys
    sys.setrecursionlimit(10 ** 7)

    n,q=map(int,input().split())

    event=[]
    for _ in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,1,x))
        event.append((t-x,-1,x))

    for i in range(q):
        event.append((int(input()),2,i))
    event.sort()

    ans=[0]*q

    stop=set()
    hq=[]
    for t,op,x in event:
        if op==1:
            heappush(hq,x)
            stop.add(x)
        elif op==-1:
            stop.remove(x)

        else:
            while hq and hq[0] not in stop:
                heappop(hq) 
            ans[x]=hq[0] if hq else -1
        
    for x in ans:
        print(x)

main()