Harryxun/stf_run huggingface dataset:
#f:やったことのある仕事=1そうでない=0
N,M = input().split()
N,M = int(N),int(M)
f_start = [0 for i in range(N)]
A,B = [],[]
for i in range(N):
    a,b = input().split()
    a,b = int(a),int(b)
    A.append(a)
    B.append(b)
    
def dp(m,f):
    if(m==0):
        return 0
    else:
        max_ = 0
        for i in range(len(A)):
            if(f[i] == 0 and A[i]<=m):
                f_co = f.copy()
                f_co[i] = 1
                max_ = max([max_,dp(m-1,f_co)+B[i]])
        
        return max_
    
print(dp(M,f_start))

### FIXED CODE ###

N,M = input().split()
N,M = int(N),int(M)
f_start = [0 for i in range(N)]
A,B = [],[]
import heapq
for i in range(N):
    a,b = input().split()
    a,b = int(a),int(b)
    A.append(a)
    B.append(-b)
    
def add(q_,add_):
    for i in range(len(add_)):
        heapq.heappush(q_,add_[i])

def kouho(A,B,M):
    kouho_list = [[] for i in range(M+1)]
    for i in range(len(A)):
        if(A[i]<=M):
            kouho_list[A[i]].append(B[i])
    return kouho_list

q = []
heapq.heapify(q)
sum_money = 0

kouho_list = kouho(A,B,M)
for m in range(1,M+1):
    kouho_ = kouho_list[m]
    add(q,kouho_)
    #print(q)
    if(len(q)>0):
        sum_money += -heapq.heappop(q)
print(sum_money)
S = input()
T = ['dream', 'dreamer', 'erase', 'eraser']
lenT = [len(i) for i in T]

def dayDream(Sres_in):
    global isDream     #;print('dayDream: ', Sres_in)
    for i, d in enumerate(T):
        #print('d:', d)
        if Sres_in[:lenT[i]] == d:            
            Sres_out = Sres_in[lenT[i]:]
            if Sres_out =='':                
                isDream = True   #; print('YES')
                return 
            else:
                dayDream(Sres_out)
    #print('return', Sres_in)
    return
    
isDream = False
dayDream(S)
if isDream:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

S = input()

T = ['dream', 'dreamer', 'erase', 'eraser']
lenT = [len(i) for i in T]

def dayDream(pin):
    global isDream               #;print('dayDream: ', pin, S[pin:])
    for i, d in enumerate(T):
        #print('d:', d)
        if S[pin:pin+lenT[i]] == d:            
            pout = pin + lenT[i] #; print(d, pout)
            if pout == len(S):                
                isDream = True   #; print('YES')
                return 
            else:
                dayDream(pout)
    #print('dayDream return', pin)
    return
    
isDream = False
dayDream(0)
if isDream:
    print('YES')
else:
    print('NO')
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
    
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


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

#if gcd(*A) % 2 != 0:
    #print(0)
    #exit(0)

#sisu_2 = factorization(A[0])[0][1] 
sisu_2 = min([factorization(A[i])[0][1] for i in range(min(1000,N))])

#lcm_a = lcm(*A)
#lcm_a_half = lcm_a // 2
lcm_a = lcm(*A) // 2
'''
l = []
sisu_a0 = 0
for i in range(N):
    sisu = 0
    while A[i]%2==0:
        A[i] //= 2
        sisu += 1
    
    if sisu_a0==0:
        sisu_a0 = sisu
    else:
        if sisu_a0!=sisu:
            print(0)
            exit()
'''
if (lcm_a % (2**sisu_2) == 0) or lcm_a > M:
#factorization(lcm_a)[0][1] != sisu_2 or lcm_a_half > M:
#if lcm_a > M:
    print(0)
    exit(0)
else:
    print(int((M-lcm_a) // (lcm_a*2) + 1))

### FIXED CODE ###

A, B = map(int, input().split())

if A * 500 >= B:
    print('Yes')
else:
    print('No')
N, M = map(int, input().split())
if not (1 <= M):
    1 // 0
if not (M * 2 + 1 <= N <= 100000):
    1 // 0

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    ans = [[] for j in range(M)]

    if N % 2:
        for i in range(M):
            ans[i].append(i + 1)
            ans[i].append(N - i - 1)
    else:
        memo = 0
        for i in range(M):
            memo = i
            if (i + 1) * 4 >= N:
                break
            ans[i].append(i + 1)
            ans[i].append(N - i - 1)
            memo += 1

        for j in range(memo, M):
            ans[j].append(j + 1)
            ans[j].append(N - j - 2)
    for a in ans:
        print(*a)


if __name__ == '__main__':
    main()
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]  # 親の値が更新され、更新された親の値が返る, 返るのは正の値

    def size(self, x):
        return -self.parents[self.find(x)]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.size(x) > self.size(y):
            x, y = y, x  # 処理を行う上で、必ずxのグループの要素数の方が多くあってほしい
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, input().split())
brige = []
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    brige.append((a, b))

uf = UnionFind(N)
ans = [int(N*(N-1)//2)]*M

for i in reversed(range(1, M)):
    if uf.same(brige[i][0], brige[i][1]):
        ans[i-1] = ans[i]
    else:
        ans[i-1] = ans[i] - uf.size(brige[i][0]) * uf.size(brige[i][1])
        uf.union(brige[i][0], brige[i][1])
for i in range(M):
    print(ans[i])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
 
class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]
		self.size = [1 for _ in range(size)]
 
	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x])
			return self.table[x]
 
	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
				self.table[s1] -= 1
				self.size[s1] += self.size[s2]
				self.size[s2] = 0
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
				self.size[s2] += self.size[s1]
				self.size[s1] = 0
 
		return
 
n, m = map(int, input().split())
brs = [list(map(int, input().split())) for _ in range(m)]
 
uf = UnionFind(n)
ans = [n*(n-1)//2]
for i in range(m-1, 0, -1):
	a, b = brs[i][0], brs[i][1]
	a, b = a-1, b-1
	s1, s2 = uf.find(a), uf.find(b)
	if s1 != s2:
		ans.append(ans[-1] - uf.size[s1]*uf.size[s2])
	else:
		ans.append(ans[-1])
	uf.union(s1, s2)
print(*list(reversed(ans)), sep="\n")
a,b =int(input().split())
if a < b:
    c = '<'
elif a > b :
    c = '>'
else:
    c = '=='
print('a %s b'%c)



### FIXED CODE ###

a,b =map(int, input().split())
if a < b:
 print('a < b')
elif a > b :
  print('a > b')
else:
 print('a == b')
#!/usr/bin/env python3

"""
https://atcoder.jp/contests/agc029/tasks/agc029_a
"""

import sys
import re



def my_sub(_re,_rep,st):
    st2 = _re.sub(_rep, st, 1)

    if st2 == st:
        return 0

    return my_sub(_re, _rep, st2) + 1



s = sys.stdin.readline().rstrip()
print(my_sub(re.compile('BW'),'WB',s))


### FIXED CODE ###

#!/usr/bin/env python3

"""
https://atcoder.jp/contests/agc029/tasks/agc029_a
"""

import sys
import re


s = sys.stdin.readline().rstrip()
e = 0
n = 0

for chr in s:
    if chr == 'W':
        e += n

    if chr == 'B':
        n += 1

print(e)
S,W = map(int,input,split)

if S <= W :
    print("unsafe")

else :
    print("safe")

### FIXED CODE ###

#入力例全てOKだけど黄色#
S,W = map(int,input().split())

if S <= W :
    print("unsafe")

else :
    print("safe")
A = input()
P = input()
ans = int((int(A) * 3  + int(P))/2)


print(ans) 

### FIXED CODE ###

A, P = input().strip().split()

ans = int((int(A) * 3  + int(P))/2)


print(ans)
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
import numpy as np

N, X, Y = map(int, input().split())
F = [[0 for i in range(N)] for j in range(N)]

for i in range(N - 1):
    F[i][i + 1] = 1
    F[i + 1][i] = 1
F[X - 1][Y - 1] = 1
F[Y - 1][X - 1] = 1

G = csgraph_from_dense(F, null_value=0)
d = dijkstra(G)

# print(F)
# print(d)

# print(np.count_nonzero(d == 1))
for i in range(1, N):
    print(np.count_nonzero(d == i) // 2)


### FIXED CODE ###

from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
import numpy as np
from collections import Counter

N, X, Y = map(int, input().split())
F = [[0 for i in range(N)] for j in range(N)]

for i in range(N - 1):
    F[i][i + 1] = 1
    F[i + 1][i] = 1
F[X - 1][Y - 1] = 1
F[Y - 1][X - 1] = 1

G = csgraph_from_dense(F, null_value=0)
d = dijkstra(G)

# print(F)
# print(d)

# print(np.count_nonzero(d == 1))
s = Counter(d.flatten().astype(np.int64))
# print(s)
for i in range(1, N):
    if i in s:
        print(s[i] // 2)
    else:
        print(0)
N, M, Q = map(int, input().split())
trains = {}
answers = {}
results = []
def make_range(L, R):
    return (pow(2, (R-L+1))-1)<<L-1

for i in range(M):
    a, b = map(int, input().split())
    train = make_range(a, b)
    if train in trains:
        trains[train] += 1
    else:
        trains[train] = 1
    
def combine_answer(answers, question, res):
    for other_question in answers:
        combine_question = other_question + question
        if other_question | question == combine_question:
            combine_res = answers[other_question] + res
            combine_answer(answers, combine_question, combine_res)
            answers[combine_question] = combine_res

for i in range(Q):
    a, b = map(int, input().split())
    question = make_range(a, b)
    if question in answers:
        results.append(answers[question])
    else:
        res = 0
        for train in trains:
            if question | train == question:
                res += trains[train]
        for other_question in answers:
            combine_question = other_question + question
            if other_question | question == combine_question:
                combine_res = answers[other_question] + res
                combine_answer(answers, combine_question, combine_res)
                answers[combine_question] = combine_res
        answers[question] = res
        results.append(res)

for result in results:
    print(result)


# 000011 + 111100 = 111111

### FIXED CODE ###

N, M, Q = map(int, input().split())

dp = [[0 for col in range(N)] for row in range(N)]

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

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

results = []

for i in range(Q):
    l, r = map(int, input().split())
    results.append(dp[l-1][r-1])

for result in results:
    print(result)
import itertools
NK = input().split()
N = NK[0]
K = int(NK[1])
 
d = input().split()
D = [int[s] for s in d]
 
Da = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 
for i in D:
    Da.remove(i)
Da_str = [str(j) for j in Da]
 
a_1 = [''.join(j) for j in itertools.product(Da_str, repeat=len(N))]
a_2 = [''.join(j) for j in itertools.product(Da_str, repeat=len(N)+1)]
a = a_1 + a_2
nu = [int(k) for k in a]
 
for i in nu:
    if i >= int(N):
        print(i)
        break

### FIXED CODE ###

import itertools
NK = input().split()
N = NK[0]
K = int(NK[1])
 
d = input().split()
D = [int(s) for s in d]
 
Da = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 
for i in D:
    Da.remove(i)
Da_str = [str(j) for j in Da]
 
a_1 = [''.join(j) for j in itertools.product(Da_str, repeat=len(N))]
a_2 = [''.join(j) for j in itertools.product(Da_str, repeat=len(N)+1)]
a = a_1 + a_2
nu = [int(k) for k in a]
 
for i in nu:
    if i >= int(N):
        print(i)
        break
N = int(input())
boxes = [0] * (N + 1)
ans = tuple(n for n, digit in reversed(tuple(enumerate(map(int, input().split()), 1))) if (sum(d for d in boxes[n::n]) & 1 != digit and (boxes.__setitem__(n, 1) or 1)))
print(f"{len(ans)}\n", *ans)

### FIXED CODE ###

N = int(input())
A = reversed(tuple(enumerate(map(int, input().split()), 1)))

boxes = [0] * (N + 1)
ans = []

for n, digit in A:
    put = sum(d for d in boxes[n::n]) & 1 != digit
    if put:
        boxes[n] = 1
        ans.append(n)

print(len(ans))
if ans:
    print(*ans)
N = int(input())
P_list = list(map(int, input().split()))
count_i = 1
for i in range(1, N):
    if P_list[i] <= min(P_list[:i+1]):
        count_i += 1
print(count_i)


### FIXED CODE ###

N, M = map(int, input().split())
if N == M:
    print('Yes')
else:
    print('No')
s=input()
s=sorted(s)

if s[1]==s[2] and s[3]==s[4] and s[1]!=s[3]:
	print('Yes')
else:
  	print('No')

### FIXED CODE ###

s=input()
s=sorted(s)
 
if s[0]==s[1] and s[2]==s[3] and s[0]!=s[2]:
	print('Yes')
else:
  	print('No')
# coding: utf-8

uSec = 1
uMinute = 60 * uSec
uHour = 60 * uMinute

input_secs = int(raw_input().rstrip())

h = input_secs / uHour
m = (input_sces - h * uHour) / uMinute
s = (input_secs - h * uHour - m * uMinute) / uSec

print ':'.join([str(x) for x in [h, m, s]])

### FIXED CODE ###

# coding: utf-8
 
uSec = 1
uMinute = 60 * uSec
uHour = 60 * uMinute
 
input_secs = int(raw_input().rstrip())
 
h = input_secs / uHour
m = (input_secs - h * uHour) / uMinute
s = (input_secs - h * uHour - m * uMinute) / uSec
 
print ':'.join([str(x) for x in [h, m, s]])
a, b = map(int, input().split())
al = []
b_lis = []

for _ in range(a):
    g = list(map(int, input().split()))
    g.append(sum(g))
    al.append(g)
for i in range(b+1):
    p = 0
    for j in range(a):
        p += al[j][i]
    b_lis.append(p)
al += b_lis
for i in al:
    print(' '.join([str(v) for v in i]))


### FIXED CODE ###

a, b = map(int, input().split())
al = []
b_lis = []

for _ in range(a):
    g = list(map(int, input().split()))
    g.append(sum(g))
    al.append(g)
for i in range(b+1):
    p = 0
    for j in range(a):
        p += al[j][i]
    b_lis.append(p)
al.append((b_lis))
for i in al:
    print(' '.join([str(v) for v in i]))
n, t = map(int, input.split())

max_cost = 10 ** 9

for _ in range(n):
  c, tt = map(int, input().split())
  if tt <= t:
    max_cost = max(max_cost, c)
    
print(max_cost)

### FIXED CODE ###

n,T=map(int,input().split())
ans=10000
for i in range(n):
  c,t=map(int,input().split())
  if t<=T:
    ans=min(ans,c)

if ans==10000:
  print("TLE")
else:
  print(ans)
n = int(input())
s1 = input()
s2 = input()
mod = 10**9 + 7
ind = []
for i,(_s1,_s2) in enumerate(zip(s1,s2)):
    if _s1 == _s2:
        ind.append(i)
# print(ind)
cnt = 0
if ind[0] == 0:
    d = 3
    single = True
    cnt = 1
else:
    d = 6
    single = False
    cnt = 2
        
while cnt < n:
    if cnt in ind: # * -> 1
        if single: 
            d *= 2
        else:#2->1
            d *= 1
        cnt += 1
        single = True
    else: # * -> 2
        if single:
            d *= 2
        else:
            d *= 3
        cnt += 2
        single =False
    d %= mod
print(d)

### FIXED CODE ###

n = int(input())
s1 = input()
s2 = input()
mod = 10**9 + 7
ind = []
for i,(_s1,_s2) in enumerate(zip(s1,s2)):
    if _s1 == _s2:
        ind.append(i)
# print(ind)
cnt = 0
if len(ind) == 0:
    d = 6
    cnt = 2
    single = False
elif ind[0] == 0:
    d = 3
    single = True
    cnt = 1
else:
    d = 6
    single = False
    cnt = 2
        
while cnt < n:
    if cnt in ind: # * -> 1
        if single: 
            d *= 2
        else:#2->1
            d *= 1
        cnt += 1
        single = True
    else: # * -> 2
        if single:
            d *= 2
        else:
            d *= 3
        cnt += 2
        single = False
    d %= mod
    
print(d)

"""
"""
import numpy as np
n = int(input())
a_lst = list(map(int,input().split()))

ans = np.prod(a_lst)
if ans > 10**18
    print("-1")
else:
    print(ans)

### FIXED CODE ###

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

ans = 1
if 0 in a_lst:
    print(0)
else:
    for a in a_lst:
        ans *= a
        if ans > 10**18:
            ans = -1
            break
    print(ans)
n = input()

def num2alpha(num):
    if num<=26:
        return chr(64+num)
    elif num%26==0:
        return num2alpha(num//26-1)+chr(90)
    else:
        return num2alpha(num//26)+chr(64+num%26)
    
print(num2alpha(n))

### FIXED CODE ###

n = int(input())

def num2alpha(num):
    if num <= 26:
        return chr(96 + num)
    elif num % 26 == 0:
        return num2alpha(num // 26 - 1) + chr(122)
    else:
        return num2alpha(num // 26) + chr(96 + num % 26)

print(num2alpha(n))
if a < x:
    a_abs = x-a
else:
    a_abs = a-x

if b < x:
    b_abs = x-b
else:
    b_abs = b-x
if a_abs > b_abs:
    print("B")
else:
    print("A")

### FIXED CODE ###

x, a, b = map(int, (input().split()))

if a < x:
    a_abs = x-a
else:
    a_abs = a-x

if b < x:
    b_abs = x-b
else:
    b_abs = b-x
if a_abs > b_abs:
    print("B")
else:
    print("A")
N = int(input())
A = map(int, input().split())
dic = {}
for i in range(N):
  if dic.get(A[i]) is None: 
    dic[A[i]] = 1
  else:
    dic[A[i]] += 1

ans = 0
for k in dic:
  if dic[k] >= k:
    ans += abs(dic[k] - k)
  else:
    ans += dic[k]
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
dic = {}
for i in range(N):
  if dic.get(A[i]) is None: 
    dic[A[i]] = 1
  else:
    dic[A[i]] += 1

ans = 0
for k in dic:
  if dic[k] >= k:
    ans += abs(dic[k] - k)
  else:
    ans += dic[k]
print(ans)
import numpy as np

q = int(input())

# 高速素数判定
is_prime = np.ones(10001, dtype=int)
is_prime[0]=0
is_prime[1]=0

for i in range(2,10001):
    if is_prime[i]==1:
        j=i+i
        while j <= n:
            is_prime[j] = 0
            j += i
            
like2017 = [is_prime[x]*is_prime[(x+1)//2] for x in range(0,10001)]

for i in range(1,n+1):
    like2017[i] += like2017[i-1]
    
for i in range(q):
    l,r = map(int, input().split())
    print(like2017[r]-like2017[l-1])


### FIXED CODE ###

import numpy as np
n=123456
q = int(input())
 
is_prime = np.ones(n+1,dtype=int)
is_prime[0]=0
is_prime[1]=0
 
for i in range(2,n+1):
    if(is_prime[i]==1):
        j=i+i
        while j <= n:
            is_prime[j] = 0
            j += i
 
cnt = [is_prime[x]*is_prime[(x+1)//2] for x in range(0,n+1)]
 
for i in range(1,n+1):
    cnt[i]+=cnt[i-1]
 
for i in range(q):
    l,r = map(int, input().split())
    print(cnt[r]-cnt[l-1])
n,m=map(int,input().split())
out=[]
for i in range(m):
  out.append(int(input()))
def stairs(n):
  memo=["a"]*n
  def count(n):
    if n in out:
      return 0
    elif n<=2:
      return n
    else memo[n-1]!="a":
      return memo[n-1]%(10e9+7)
    return (memo[n-2]+memo[n-3])%(10e9+7)
  return count(n)
print(stairs(n)%(10e9+7))

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
arr=[1,2]
arr=arr+[0]*(n-2)
danger=[int(input()) for _ in range(m)]
if danger==[]:
  pass
elif danger[0]==1:
  arr[0]=0
  arr[1]=1
for i in range(m):
  arr[danger[i]-1]=-1
for i in range(n):
  if arr[i]==-1:
    arr[i]=0
  elif i==0 or i==1:
    continue 
  else:
    arr[i]=(arr[i-1]+arr[i-2])%(10**9+7)
print(arr[n-1]%(10**9+7))
a,b,c = (str(x) for x in input().split())
if a == b == c:
    print(No)
else:
    print(Yes)

### FIXED CODE ###

S = input()
if S[0] == S[1] == S[2]:
    print('No')
else:
    print('Yes')
from itertools import combinations
n, m, x = map(int, input().split())
ca = list(map(int, input().split()))

ans = 10**9
for i in range(1,n+1):
  for j in combinations(ca, i):
    s = [0]*(m+1)
    for k in j:
      for l in range(m+1):
        s[l] += k[l]
    if min(s[1:]) <= x:
      ans += min(ans, s[0])
if ans == 10**9:
  print(-1)
else:
  print(ans)
    

### FIXED CODE ###

from itertools import combinations
n, m, x = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(n)]

ans = 10**10
for i in range(1,n+1):
  for j in combinations(ca,i):
    check = [0]*(m+1)
    for k in j:
      for a in range(m+1):
        check[a] += k[a]
    if min(check[1:]) >= x:
      ans = min(ans, check[0])

if ans == 10**10:
  print(-1)
else:
  print(ans)
import sys
#sys.setrecursionlimit(450000)
input = sys.stdin.readline

from functools import lru_cache


@lru_cache(maxsize=None)
def Tsundoku(i,j):
    global k
    #if dp[i][j]!=None:
    #    return dp[i][j]
    ans1,ans2 = 0,0
    if i<n and k-a[i]>=0:
        k-=a[i]
        ans1 = 1+Tsundoku(i+1,j)
        k+=a[i]
    if j<m and k-b[j]>=0:
        k-=b[j]
        ans2 = 1+Tsundoku(i,j+1)
        k+=b[j]
    #dp[i][j] = max(ans1,ans2)
    #return dp[i][j]
    return max(ans1,ans2)

n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
#dp = [[None]*(m+1) for _ in range(n+1)]
ans = Tsundoku(0,0)
print(ans)

### FIXED CODE ###

from itertools import accumulate

def bs(t):
    l,h = 0,len(b)-1
    while l<=h:
        m = (l+h)//2
        if b[m]<t:
            l=m+1
        elif b[m]>t:
            h=m-1
        else:
            return m
    return h

n,m,k = map(int,input().split())
a = list(accumulate([0]+list(map(int,input().split()))))
b = list(accumulate([0]+list(map(int,input().split()))))
ans = 0
for idx,i in enumerate(a):
    if i<=k:
        #print(idx,bs(k-i))
        ans = max(ans,bs(k-i)+idx)
print(ans)
def f(A,B):
    m=0
    for i in range(len(A)):
        if m<A[i]+B[i]:
            m=A[i]+B[i]
    return m

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

B=[[0 for _ in range(J)] for __ in range(N)]
for i in range(N):
    m=A[i]
    for j in range(J):
        B[i][j]=m%2
        m>>=1
B+=[[float("inf")]*J]

b=0
X=[0]*J
K=0

for a in range(N):
    while f(X,B[b])<=1:
        for k in range(J):
            X[k]+=B[b][k]
        b+=1

    K+=b-a

    for k in range(N):
        X[k]-=B[a][k]

print(K)

### FIXED CODE ###

def f(A,B):
    m=0
    for i in range(len(A)):
        if m<A[i]+B[i]:
            m=A[i]+B[i]
    return m

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

B=[[0 for _ in range(J)] for __ in range(N)]
for i in range(N):
    m=A[i]
    for j in range(J):
        B[i][j]=m%2
        m>>=1
B+=[[float("inf")]*J]

b=0
X=[0]*J
K=0

for a in range(N):
    while f(X,B[b])<=1:
        for k in range(J):
            X[k]+=B[b][k]
        b+=1

    K+=b-a

    for k in range(J):
        X[k]-=B[a][k]

print(K)
N=input()
s=0
for i in N:
  if i=='1':
    s++

print(s)    


### FIXED CODE ###

N=input()
s=0
for i in N:
  if i=="1":
    s=s+1

print(s)
from math import factorial

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

x = 1000000007

num = factorial(N - K + 1) * factorial(K - 1)

for i in range(1, K + 1):
    denom = factorial(i) * factorial(N - K + 1 - i) * factorial(i - 1) * factorial(K - i)
    v = num // denom

    print(v % x)


### FIXED CODE ###

from math import factorial

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

x = 1000000007

num = factorial(N - K + 1) * factorial(K - 1)

for i in range(1, K + 1):
    if N - K < i - 1:
        print(0)
    else:
        denom = factorial(i) * factorial(N - K + 1 - i) * factorial(i - 1) * factorial(K - i)
        v = num // denom

        print(v % x)
n,m=map(int, input().split())
A=[int(i) for i in input().split()]
A.sort()
bc=[]
for i in range(m):
    b,c=map(int, input().split())
    bc.append([b,c])
bc.sort(key = lambda x:x[1], reverse=True)
count=0
for i in bc:
    for j in range(i[0]):
        if A[count]<i[1]:
            A[count]=i[1]
            count+=1
        else:
            break
print(sum(A))


### FIXED CODE ###

n,m=map(int, input().split())
A=[int(i) for i in input().split()]
tmp = min(A)
A.sort()
ab=[]
for i in range(m):
    b,c=map(int, input().split())
    if not c<tmp:
        ab.append([b, c])
ab.sort(key=lambda x:x[1], reverse = True)
f=False
a = 0
for i in range(len(ab)):
    for j in range(min(ab[i][0], n)):
        if A[a]>ab[i][1]:
            f=True
            break
        A[a]=ab[i][1]
        a+=1
        if a==n:
            f=True
            break
    if f==True:break
print(sum(A))