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

#coding:utf-8

def main():
    h, n = map(int, input().split())
    ab = []
    for _ in range(n):
        ab.append(list(map(int, input().split())))
    
    inf = 100000000000
    # indexがモンスターに与えたダメージで、中身がトキのダメージ
    damages = [0] + [inf] * h
    for i in range(1, h + 1):
        for j in range(n):
            damage_monster = ab[j][0]
            damage_toki = ab[j][1]
            
            damages[i] = min(damages[max(0, i - damage_monster)] + damage_toki, damages[i])


    print(min(damages[h:]))
main()

### FIXED CODE ###

#coding:utf-8

def main():
    h, n = map(int, input().split())
    ab = []
    for _ in range(n):
        ab.append(list(map(int, input().split())))
    
    inf = 100000000000
    # indexがモンスターに与えたダメージで、中身がトキのダメージ
    damages = [0] + [inf] * h
    for i in range(1, h + 1):
        for j in range(n):
            damage_monster = ab[j][0]
            damage_toki = ab[j][1]
            
            damages[i] = min(damages[max(0, i - damage_monster)] + damage_toki, damages[i])


    print(min(damages[h:]))
main()
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
ans = 0
L_count = 0
L_dict = dict()
for i in range(N):
    for j in range(i+1,N):
        for l in range(j+1,N):
            a = L[i]
            b = L[j]
            c = L[l]
            if a < (b+c):
                if b < (c+a):
                    if c < (a+b):
                        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
ans = 0
L.sort()
from bisect import bisect_left
for i in range(N):
    for j in range(i+1,N):
        #三角形の辺を2つ固定する
        t = L[i] + L[j]
        #配列のindexが返される。
        idx = bisect_left(L,t)
        #2番目に長い辺jより長い、かつ、2辺の和よりも小さい辺の数を求める。
        # t自体を含めないため、-1をしている。
        ans += max(0,idx - j -1)
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N=int(input())

print(N-1)
if input()=="Vacant":
    exit()
print(0)
who=input()
if who=="male":
    start=0
elif who=="female":
    start=1
else:
    exit()

high=N-1
low=0
while True:
    mid=(high+low)//2
    print(mid)
    who=input()
    if who=="male":
        temp=0
    elif who=="female":
        temp=1
    else:
        exit()
    
    if (mid%2)^start==temp:
        low=mid
    else:
        high=mid
    


### FIXED CODE ###

# coding: utf-8
# Your code here!
N=int(input())

print(N-1)
if input()=="Vacant":
    exit()
print(0)
who=input()
if who=="Male":
    start=0
elif who=="Female":
    start=1
else:
    exit()

high=N-1
low=0
while True:
    mid=(high+low)//2
    print(mid)
    who=input()
    if who=="Male":
        temp=0
    elif who=="Female":
        temp=1
    else:
        exit()
    
    if (mid%2)^start==temp:
        low=mid
    else:
        high=mid
### BUGGY CODE ###

import copy
import math

n,x = map(int,raw_input().split())
s = map(int,raw_input().split())

s.sort(reverse=True)
ans = 0

def dfs(xx,ss):
  ans = 0
  if len(ss)==1:
    return xx % ss[0]

  for q in ss:
    x2 = xx % q
    s2 = copy.deepcopy(ss)
    s2.remove(q)
    if x2 < min(s2):
      ans += math.factorial( len(s2) ) * x2
    else:
       ans += dfs(x2,s2)
  return ans

print dfs(x,s) % (10**9 + 7)


### FIXED CODE ###

import copy
import math

N,X = map(int,raw_input().split())
S = map(int,raw_input().split())
MOD = 10**9 + 7

S.sort()

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

for i in range(X+1):
  dp[1][i] = i % S[0]

for n in range(2,N+1):
  for x in range(X+1):
    #print n,x
    dp[n][x] =  dp[n-1][x] * (n-1) 
    dp[n][x] += dp[n-1][x%S[n-1]]
    dp[n][x] %= MOD

print dp[N][X]
### BUGGY CODE ###

s = input()
s_len = int(len(s))
count = 0
n = int(s_len*(s_len+1)/2)
for _ in range(n):
  num = s.count('BW')
  if num == 0:
    break
  s = s.replace('BW','WB')
  count += num
print(count)

### FIXED CODE ###

S = list(input())
W_i = [i for i,j in enumerate(S) if j == 'W']
W_n = S.count('W')
cur = 0
ans = 0
for i in W_i:
  ans += i-cur
  cur += 1
print(ans)
### BUGGY CODE ###

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

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

L.sort()

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#print(L)
mod=10**9+7
ans=0
for i in range(K-1,len(L)): #ピッチ
    for j in range(len(L)): #スタート
        if i+j<len(L):
            ans+=(L[j+i]-L[j])*cmb(i-1,K-2,mod)
            #print(j,i,cmb(i,K-2,mod))
    ans%=mod
print(ans)
                

### FIXED CODE ###

n,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
mod=10**9+7



def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 #出力の制限
N = 10**5+5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
L=[]
for i in range(n):
    L.append(cmb(n-1-i,K-1,mod))
#print(L)
Small=0
for i in range(n):
    Small+=A[i]*L[i]
    Small%mod
    
Big=0
RA=A[::-1]
for i in range(n):
    Big+=RA[i]*L[i]
    Big%=mod
print((Big-Small)%mod)
### BUGGY CODE ###

N = int(input())
dlist = list(map(int, input().split()))
dlist.sort(reverse=True)
sum = 0
N_2 = 2 ** N
for i in range(N_2):
    if bin(i).count('1') == 3:
        bin_i = bin(i)
        i_2 = bin_i.split('0b')[1]
        if len(i_2) < N:
            N_i = (N - len(i_2))
            N_0 = '0' * N_i
            i_2 = N_0 + i_2
        a_find = i_2.find('1')
        b_find = i_2.find('1',a_find + 1)
        c_find = i_2.find('1',b_find + 1)
        a = dlist[a_find]
        b = dlist[b_find]
        c = dlist[c_find]
        if a < b + c:
            sum += 1
print(sum)

### FIXED CODE ###

import bisect
N=int(input())
L=sorted(list(map(int,input().split())))

ans=0
for i in range(N-2):
  for j in range(i+1,N-1):
    ans+=bisect.bisect_left(L,L[i]+L[j])-j-1 # Code 1 
    # ans+=bisect.bisect_left(L,L[i]+L[j],j)-j-1 # Code 2 
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
dice = list(map(int,input().split()))

dice_cumsum = [0]*200001
dice_cumsum[1] = 1

for i in range(2,200001):
    dice_cumsum[i] = dice_cumsum[i-1]+i


max_n = 0
max_i = 0
for i in range(n-k+1):
    sum_dice = sum(dice[i:k+i])
    if sum_dice > max_n:
        max_n = sum_dice
        max_i = i

sum_odds = 0
for i in range(k):
    sum_odds += dice_cumsum[dice[max_i+i]]/dice[max_i+i]
    
print(sum_odds)

### FIXED CODE ###

n,k = map(int,input().split())
dice = list(map(int,input().split()))

dice_cumsum = [0]*(n+1)

for i in range(1,n+1):
    dice_cumsum[i] = dice_cumsum[i-1] + dice[i-1]
    
max_n = 0
max_i = 0
for i in range(n-k+1):
    sum_dice = dice_cumsum[k+i] - dice_cumsum[i]
    if sum_dice > max_n:
        max_n = sum_dice
        max_i = i

sum_odds = 0
for i in range(k):
    sum_odds += (dice[max_i+i]-1)*0.5+1

print(sum_odds)
### BUGGY CODE ###

n,m = map(int, raw_input().split(' '))
keys = set(range(1,n+1))
for _ in range(m):
	a,b = map(int, raw_input().split(' '))
	keys = keys.intersection(set( range(a,b+1)  ))
	if len(keys) == 0: break
print len(keys)


### FIXED CODE ###

n,m = map(int, raw_input().split(' '))
def intersection(A,B):
	a,b  = max(A[0],B[0]), min(A[1],B[1])
	return [a,b] if a <= b else []

r = [1,n+1]
for _ in range(m):
	a,b = map(int, raw_input().split(' '))
	r = intersection(r, [a,b])
	if len(r) == 0: break
print (r[1] - r[0] + 1) if r else 0
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)

from functools import lru_cache

def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]
 
    dp = [0] * W
    memo = [0] * N 
    
    @lru_cache(maxsize=None)
    def dfs(w, v, i):
        if w > W:
            return 0
        if i >= N:
            return v
        return max(dfs(w + w_v[i][0], v + w_v[i][1], i+1), dfs(w, v, i+1))

    res = dfs(0, 0, 0)
    print(res)


if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]

    dp = [[0] * (W+1) for _ in range(N+1)] 

    for i in range(N-1,-1,-1):
        for j in range(W+1):
            w = w_v[i][0]
            v = w_v[i][1]
            if j < w_v[i][0]:
                dp[i][j] = dp[i+1][j]
            else:
                dp[i][j] = max(dp[i+1][j], dp[i+1][j - w] + v)
 
    print(dp[0][W])
 
if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

N,K,L = map(int,input().split())
roads = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(K)]
rails = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(L)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf_road = UnionFind(N)
for a,b in roads:
    if uf_road.is_same(a,b): continue
    uf_road.unite(a,b)

uf_rail = UnionFind(N)
for a,b in rails:
    if uf_rail.is_same(a,b): continue
    uf_rail.unite(a,b)

for i in range(N):
    uf_road.root(i)
    uf_rail.root(i)

road_sets = [None] * N
for i in range(N):
    r = uf_road.root(i)
    if not road_sets[r]:
        road_sets[r] = set()
    road_sets[r].add(i)

rail_sets = [None] * N
for i in range(N):
    r = uf_rail.root(i)
    if not rail_sets[r]:
        rail_sets[r] = set()
    rail_sets[r].add(i)

ans = []
for i in range(N):
    r1 = uf_road.root(i)
    r2 = uf_rail.root(i)
    cnt = len(road_sets[r1] & rail_sets[r2])
    ans.append(cnt)
print(*ans)

### FIXED CODE ###

from collections import Counter
N,K,L = map(int,input().split())

p_road = [i for i in range(N)]
p_rail = [i for i in range(N)]

def root(a,par):
    if a == par[a]: return a
    par[a] = root(par[a],par)
    return par[a]

def unite(a,b,par):
    ra = root(a,par)
    rb = root(b,par)
    if ra == rb: return
    par[ra] = rb

for i in range(K):
    a,b = map(lambda x:int(x)-1, input().split())
    unite(a,b,p_road)

for i in range(L):
    a,b = map(lambda x:int(x)-1, input().split())
    unite(a,b,p_rail)

road_ids = []
rail_ids = []
for i in range(N):
    road_ids.append(root(i,p_road))
    rail_ids.append(root(i,p_rail))

ctr = Counter()
for a,b in zip(road_ids, rail_ids):
    ctr.update([(a,b)])

print(' '.join(list(map(str, [ctr[(road_ids[i], rail_ids[i])] for i in range(N)]))))
### BUGGY CODE ###

from collections import deque
N = int(input())
st = deque()
push, pop = st.appendleft, st.pop

for n in range(N-1):
    push([int(i) for i in input().split()])

dist = [0]*N
cnt = [0]*N

[u,v,w] = pop()
dist[v-1] = dist[u-1] + w 
cnt[u-1],cnt[v-1] = 1,1
while st:
    [u,v,w] = pop()
    if cnt[u-1] == 1:
        dist[v-1] = dist[u-1] + w 
        cnt[u-1],cnt[v-1] = 1,1
    elif cnt[v-1] == 1:
        dist[u-1] = dist[v-1] + w 
        cnt[u-1],cnt[v-1] = 1,1
    else:
        push([u,v,w])



for d in dist:
    if d%2 == 0:
        print(0)
    else:
        print(1)


### FIXED CODE ###

from collections import deque
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    u,v,w = map(int, input().split())
    G[u-1].append((v-1, w))
    G[v-1].append((u-1, w))

st = deque()
push, pop = st.appendleft, st.pop
push(0)
dist = [0]*N
cnt = [0]*N
cnt[0] = 1

while st:
    u = pop()
    for v,w in G[u]:
        if cnt[v] == 1:
            continue
        dist[v] = dist[u] + w
        push(v)
        cnt[v] = 1

for d in dist:
    if d%2 == 0:
        print(0)
    else:
        print(1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np
A, B = map(int, input().split())
pn = [2]
C = max(A, B)
for i in range(3, C+1):
  flag = 0
  for k in pn:
    if(i%k == 0):
      flag = 1
      break
  if(flag == 0):
    pn.append(i)
#print(pn)

N = len(pn)
aa = np.zeros(N)
bb = np.zeros(N)
As = A
Bs = B
for k in range(N):
  flag = 1
  count = 0
  while(flag == 1):
    if(As % pn[k] == 0):
      As = As // pn[k]
      count += 1
    else:
      flag = 0
  aa[k] = count

  flag = 1
  count = 0
  while(flag == 1):
    if(Bs % pn[k] == 0):
      Bs = Bs // pn[k]
      count += 1
    else:
      flag = 0
  bb[k] = count

ans = 1
for k in range(N):
  ans *= pn[k] ** max(aa[k], bb[k])

print(int(ans))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
A, B = map(int, input().split())

L = max(A, B)
S = min(A, B)
flag = 1
while(flag == 1):
  #print(L, S)
  if(L % S == 0):
    flag = 0
    lval = S
  else:
    tmp = L % S
    L = S
    S = tmp

Ar = A // lval
Br = B // lval

print(int(lval*Ar*Br))
### BUGGY CODE ###

s = input()
l = len(s)

while True:
  if '01' in s or '10' in s:
    s = s.replace('01', '')
    s = s.replace('10', '')
  else:
    break

print(l - len(s))
    

### FIXED CODE ###

s = input()
print(2 * min([sum([v == '1' for v in s]), sum([v == '0' for v in s])]))
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()
    # N = 39
    # S = 'RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB'
    
    # ######### Index
    # R, G, B = [], [], []
    # for i, s in enumerate(S):
    #     if s == 'R':
    #         R.append(i)
    #     elif s == 'G':
    #         G.append(i)
    #     elif s == 'B':
    #         B.append(i)
    
    C = 0
    out = 0
    # for i in R:
    # for i in B:
    # for i in range(len(S)):
        
        
    #     # for j in G:
    #     # for j in B:
    #     for j in range(i+1, len(S)):
            

    #         # for k in B:
    #         # for k in G:
    #         # for k in R:
    #         for k in range(j+1, len(S)):
                
    #             # print(i, j, k)
                
    #             if not (j - i) == (k - j):
    #                 if (S[i] != S[j]) and (S[i] != S[k]) and (S[k] != S[j]):
                    
                        
    #                     out += 1
    
    combinations = [[i, j, k]
                for i in range(len(S))
                for j in range(i+1, len(S))
                for k in range(j+1, len(S))
                ]
    # print(combinations)
    
    for i, j, k in combinations:
        if not (j - i) == (k - j):
            if (S[i] != S[j]) and (S[i] != S[k]) and (S[k] != S[j]):
            
                
                out += 1



    print(out)

    
main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(300000)
from collections import defaultdict
 
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')
 
 
N = I()
S = input()

# N = 39
# S = 'RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB'
 
d = defaultdict(int)
for c in S:
    d[c] += 1
plus = d['R'] * d['G'] * d['B']

# print(plus)
 
minus = 0
for j in range(1, N - 1):
    for l in range(1, N):
        i, k = j - l, j + l
        if i < 0 or k > N - 1:
            break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            minus += 1
 
print(plus - minus)
### BUGGY CODE ###

n = int(input())
S = input()
cnt = 0
for i in range(0, 1000):
  c = [i//100, (i//10)%10, i%10]
  f = 0
  for j in range(len(S)):
    if int(S[j]) == c[f]:
      f += 1
    if f==3:
      break 
  if f==3:
    cnt += 1
print(cnt)

### FIXED CODE ###

input()
S = [int(i) for i in input()]
cnt = 0
for i in range(0, 1000):
  c = (i//100, (i//10)%10, i%10)
  f = 0
  for s in S:
    if s == c[f]:
      f += 1 
      if f==3:break 
  if f==3:cnt += 1
print(cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
listsum = 0
for i in range(n-1):
    for j in range(i+1,n):
        listsum += a[i]*a[j]%mod
        listsum = listsum%mod
print(listsum)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
listsum = sum(a)
kotae = 0
for i in range(n-1):
    listsum -= a[i]
    kotae += listsum*a[i]%mod

print(kotae%mod)
### BUGGY CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [0] * n
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])
    if n == 2:
        print(dp[1])
    else:
        for i in range(2, n):
            if i <= k:
                dp[i] = min(abs(h[i] - h[i - j]) + dp[i - j] for j in range(1, i + 1))
            else:
                dp[i] = min(abs(h[i] - h[i - j]) + dp[i - j] for j in range(1, k + 1))
        print(dp[n - 1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [0] * n
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])

    for i in range(2, n):
        dp[i] = min(abs(h[i] - h[j]) + dp[j] for j in range(max(0, i - k), i))
    print(dp[n - 1])


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

h,w,d = [int(i) for i in input().split()]
a = []
for i in range(0,h):
    a.append(input().split())
for i in range(0,h):
    for j in range(0,w):
        a[i][j] = int(a[i][j])
q = int(input())
lr = []
for i in range(0,q):
    lr.append(input().split())
    
def abs(c): 
    if c > 0: 
        return c 
    else: 
        return -c
    
def distance_2d(a,b):
    return(abs(a[0]-b[0])+abs(a[1]-b[1]))
    
def list_1d(d,v):
    return [ v for i in range(d)]

def search_2d(a,key):
    x = -1
    y = -1
    for i in range(0,len(a)):
        for j in range(0,len(a[0])):
            if a[i][j] == key:
                x = i
                y = j
        if x != -1:
            break
    
    return([x,y])

sa = list_1d(h*w,[])

for i in range(0,h*w):
    sa[i] = search_2d(a,i+1)



for i in range(0,q):
    present = int(lr[i][0])
    goal = int(lr[i][1])
    power = 0
    while present != goal:
        power += distance_2d(sa[present-1],sa[present+d-1])
        present += d
    print(power)
        
    
    

### FIXED CODE ###

def list_1d(d,v):
    return [ v for i in range(d)]

def abs(c): 
    if c > 0: 
        return c 
    else: 
        return -c

def distance_2d(a,b):
    return(abs(a[0]-b[0])+abs(a[1]-b[1]))

h,w,d = [int(i) for i in input().split()]
sa = list_1d(h*w+1,[])
da = list_1d(h*w+1,0)
for i in range(h):
    a = [int(k) for k in input().split()]
    for j in range(w):
        sa[a[j]] = [i,j]
q = int(input())
lr = [[int(i) for i in input().split()] for i in range(q)]

for i in range(d+1,h*w+1):
    da[i] = da[i-d] + distance_2d(sa[i],sa[i-d])

for i in range(0,q):
    print(da[lr[i][1]]-da[lr[i][0]])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(1, n+1):
    print(a.index(i)+1,end=" ")
print()

### FIXED CODE ###

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


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

wv = [[0 for i in range(2)] for j in range(N+1)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    wv[i+1][0],wv[i+1][1] = map(int, input().split())

sorted(wv)

for i in range(N):
    Wsum[i+1] = Wsum[i] + wv[i+1][0]
    Vsum[i+1] = Vsum[i] + wv[i+1][1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #制約が0のときも価値は0
    if W2 == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は入れられない
    if W2 < wv[i][0]:
        return nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値
    if Wsum[i] <= W2:
        return Vsum[i]

    return max( nap(i-1,W2-wv[i][0])+wv[i][1] , nap(i-1,W2) )
    
            
print(nap(N,W))


### FIXED CODE ###


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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    w[i],v[i] = map(int, input().split())
Wmin = min(w)

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #重複計算を避けるためnap(i,W2)を保持
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    #品物0個のときは価値は0
    elif i == 0:
        r = 0
    #制約0のときも価値は0
    elif W2 < Wmin:
        r = 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    elif W2 < w[i]:
        r = nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    elif Wsum[i] <= W2:
        r = Vsum[i]
    #i番目の品物をナップサックに入れるか入れないか
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

def main():
    N, M = mi()
    A = sorted(li())

    '''
    for j in range(M):
        b, c = mi()
        ind = min(bisect.bisect_left(A, c), b)
        A = sorted([c]*ind + A[ind:])
    
    print(sum(A))
    '''
    for _ in range(M):
        b, c = mi()
        for _ in range(b):
            A.append(c)
        
    print(sum(sorted(A, reverse=True)[:N]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

def main():
    N, M = mi()
    A = sorted(li())

    '''
    for j in range(M):
        b, c = mi()
        ind = min(bisect.bisect_left(A, c), b)
        A = sorted([c]*ind + A[ind:])
    
    print(sum(A))
    '''
    ab = li2(M)
    ab.sort(key=lambda x: x[1], reverse=True)
    c_list = []
    l = 0
    for b, c in ab:
        if l + b > N:
            c_list += [c]*(N-l)
            l = N
        else:
            c_list += [c]*b
            l += b
        if l == N:
            break
    ans = sum(sorted(A+c_list, reverse=True)[:N])
    print(ans)

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

n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))

max_z = 0
for i in range(2**n):
  #print("i:",i)
  x = 0
  y = 0
  for j in range(n):
    if i&(1<<j)!=0:
      #print('j:',j)
      x+=v[j]
      y+=c[j]
  z=x-y
  #print(z)
  max_z = max(max_z,z)
print(max_z)
  


### FIXED CODE ###

n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))

max_z = 0
for i in range(2**n):
  #print("i:",i)
  x = 0
  y = 0
  for j in range(n):
    if i&(1<<j)!=0:
      #print('j:',j)
      x+=v[j]
      y+=c[j]
  z=x-y
  #print(z)
  max_z = max(max_z,z)
print(max_z)