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

import sys

def solve():
    N = int(input())
    S = input()
    words = dict()
    longest = 0
    for i in range(N-1):
        current = S[i]
        if current in words: longest = max(longest, 1)
        else: words[current] = i
        for j in range(1, N - i):
            current += S[i + j]
            if current in words:
                if words[current] + j + 1 <= i: longest = max(longest, j + 1)
            else: words[current] = i
    if S[N-1] in words: longest = max(longest, 1)

    #print(words)

    print(longest)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys

def solve():
    N = int(input())
    S = input()
    lens = len(S)
    alp = ["a", "b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u",\
        "v","w","x","y","z"]
    
    DP = [[0 for j in range(lens)] for i in range(lens)]
    DP[lens - 2][lens - 1] = (1 if S[lens-2] == S[lens - 1] else 0)
    for i in reversed(range(lens - 1)):
        for j in reversed(range(i + 1, lens)):
            if S[i] == S[j]:
                if j == lens - 1: DP[i][j] = 1
                else: DP[i][j] = DP[i+1][j+1] + 1

    maxlength = 0
    for i in range(lens):
        for j in range(i+1, lens):
            maxlength = max(maxlength, min(DP[i][j], j - i))

    print(maxlength)
    return 0

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

if __name__ == '__main__':

	INF = 10**18
	
	n = int(input())
	A = list(map(int,input().split()))

	ans = 1
	flg = False

	for i in range(n):
		if A[i] == 0:
			ans = 0
			break
		ans = ans * A[i]

	if ans > INF:
		print(-1)
	else:
		print(ans)


### FIXED CODE ###

if __name__ == '__main__':

	INF = 10**18
	
	n = int(input())
	A = list(map(int,input().split()))

	if 0 in A:
		print(0)
		exit()

	ans = 1
	flg = False

	for i in range(n):
		ans = ans * A[i]
		if ans > INF:
			ans = -1
			break

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

# coding: utf-8
import math
import numpy
#N = int(input())
N, K = map(int,input().split())
A = list(map(int,input().split()))
#K =int(input())
ANS = []
for i in range(K-1, N):
    a = 1
    for j in range(i-K+1,i+1):
        a *= A[j]
    ANS.append(a)
#print(ANS)
for i in range(N-K):
    if ANS[i+1] > ANS[i]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

# coding: utf-8
#import math
#import numpy
#N = int(input())
def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    #K =int(input())
    ANS = []
    
    #ANS.append(a)
    for i in range(K,N):
        if A[i-K] < A[i]:
            print("Yes")
        else:
            print("No")
        
        
        #ANS.append(a)
    #print(ANS)
    

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

n=int(input())
m=list(map(int,input().split()))
x=1
if 0 in m:
  print(0)
else:
  for y in m:
    x*=y
  if x>10**18:
    print(-1)
  else:
    print(x)



### FIXED CODE ###

# coding: utf-8

n = int(input())
numlist = list(map(int, input().split()))
ans = 1;

if 0 in numlist:
    ans = 0
else:
    for i in numlist:
        ans *= i
        if ans > 10**18:
            ans = -1
            break

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

import sys
input = sys.stdin.buffer.readline
n,ma,mb=map(int,input().split())
ABC=[list(map(int,input().split())) for _ in range(n)]
infi=10**15
dp=[[[infi]*(401) for _ in range(401)]for _ in range(41)]
dp[0][0][0]=0
for i in range(n):
    a,b,c=ABC[i]
    for j in range(401-a):
        for k in range(401-b):
            ni=i+1
            nj=j+a
            nk=k+b
            dp[ni][j][k]=min(dp[ni][j][k], dp[i][j][k])
            dp[ni][nj][nk]=min(dp[i][j][k]+c,dp[ni][nj][nk])

ans=infi
for i in range(1,401):
    if ma*i>400:
        break
    if mb*i>400:
        break    
    ans=min(ans, dp[n][ma*i][mb*i])
print(ans if ans!=infi else -1)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
n,ma,mb=map(int,input().split())
ABC=[list(map(int,input().split())) for _ in range(n)]
infi=10**15
dp=[[[infi]*(401) for _ in range(401)]for _ in range(41)]
dp[0][0][0]=0
for i in range(n):
    a,b,c=ABC[i]
    for j in range(401-a):
        for k in range(401-b):
            ni=i+1
            nj=j+a
            nk=k+b
            dp[ni][j][k]=min(dp[ni][j][k], dp[i][j][k])
            dp[ni][nj][nk]=min(dp[i][j][k]+c,dp[ni][nj][nk])

ans=infi
for i in range(1,401):
    if ma*i>400:
        break
    if mb*i>400:
        break    
    ans=min(ans, dp[n][ma*i][mb*i])
print(ans if ans!=infi else -1)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline


N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
day = 0
cnt = N
while cnt:
    flag = True
    Done = [False] * N
    for i, a in enumerate(A):
        if len(a) == 0:
            continue
        if Done[i]:
            continue
        x = a[-1] - 1
        if A[x] and (not Done[x]) and (A[x][-1] - 1 == i):
            A[i].pop()
            A[x].pop()
            Done[i] = True
            Done[x] = True
            flag = False
            if not A[i]:
                cnt -= 1
            if not A[x]:
                cnt -= 1

    if flag:
        break
    day += 1
if cnt:
    print(-1)
else:
    print(day)

### FIXED CODE ###

import sys
# input = sys.stdin.buffer.readline


N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
day = 0
cnt = N
Last = set([i for i in range(N)])
while cnt:
    flag = True
    Done = [False] * N
    L = set()
    for i in Last:
        if len(A[i]) == 0:
            continue
        if Done[i]:
            continue
        x = A[i][-1] - 1
        if A[x] and (not Done[x]) and (A[x][-1] - 1 == i):
            A[i].pop()
            A[x].pop()
            Done[i] = True
            Done[x] = True
            L.add(i)
            L.add(x)
            flag = False
            if not A[i]:
                cnt -= 1
            if not A[x]:
                cnt -= 1
    Last = L
    if flag:
        break
    day += 1
if cnt:
    print(-1)
else:
    print(day)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = []
for i in range(n-k+1):
    ans.append((sum(p[(i):(k+i)])+k)/2)
print(max(ans))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
tmp = sum(p[:k])
ans = [tmp]
if n == k:
    ans_mae = ans[0]
    print((ans_mae+k)/2)
else:
    for i in range(1,n-k+1):
        tmp = tmp - p[i-1] + p[i+k-1]
        ans.append(tmp)
    print((max(ans)+k)/2)
### BUGGY CODE ###

import bisect

N = int(input())
Ls = list(map(int, input().split()))
Ls.sort()
# index: 0,...,N-1

ans = 0
print(sum(bisect.bisect_left(Ls[j+1:], J + I) for i,I in enumerate(Ls[:-2]) for j,J in enumerate(Ls[i+1:-1], start=i+1)))
    # i: 0,...,N-3
    # j: i+1,...,N-2
    # k: j+1,...,N-1


### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort() # index: 0,...,N-1

ans = 0
for i in range(N-2): # i: 0,...,N-3
    for j in range(i+1, N-1): # j: i+1,...,N-2
        # k の満たすべき条件:
        # 1. L[k] > L[j] - L[i]
        #     L[k] > L[j] なので自動的に満たす
        # 2. L[k] < L[i] + L[j]
        x = bisect.bisect_left(L, L[i]+L[j])
        # (<L[i]+L[j]), (<L[i]+L[j]), ..., (<L[i]+L[j]) | (L[i]+L[j]<=), (L[i]+L[j]<=), ...
        # | (x) より左側はOK
        # j+1 より右側はOK
        # L[j]<L[i]+L[j] と L[i]+L[j]<=L[x] より L[j]<L[x] つまり j<x
        ans += x - (j + 1)

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

from collections import deque

dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
H, W = map(int, input().split())
edge = ['#']*(W+2)
field = [edge]
q = deque()

for i in range(H):
    field.append(['#'] + list(input()) + ['#'])
    for j in range(W):
        if field[i+1][j+1] == '#':
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    res = max(lv, res)

    for dy, dx in dyx:
        if not field[y+dy][x+dx] == '#':
            field[y+dy][x+dx] = '#'
            q.append((y+dy, x+dx, lv+1))

print(res)


### FIXED CODE ###

from collections import deque

dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
H, W = map(int, input().split())
edge = ['#']*(W+2)
field = [edge]
q = deque()

for i in range(H):
    field.append(['#'] + list(input()) + ['#'])
    for j in range(W):
        if field[i+1][j+1] == '#':
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    res = max(lv, res)

    for dy, dx in dyx:
        if field[y+dy][x+dx] == '.':
            field[y+dy][x+dx] = '#'
            q.append((y+dy, x+dx, lv+1))

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

s=input()
n=int(input())
f=0
l=""
r=""
for i in range(n):
	q=input().split()
	if q[0]=="1":
		f^=1
	else:
		if (f==0 and q[1]=="1") or (f==1 and q[1]=="2"):
			l=l+q[2]
		else:
			r=r+q[2]

if f==0:
	ans=l[::-1]+s+r
else:
	ans=r[::-1]+s[::-1]+l

print(ans)







### FIXED CODE ###

s=input()
n=int(input())
f=0
l=""
r=""
for i in range(n):
	q=input().split()
	if q[0]=="1":
		f^=1
	else:
		if (f==0 and q[1]=="1") or (f==1 and q[1]=="2"):
			l=l+q[2]
		else:
			r=r+q[2]

if f==0:
	ans=l[::-1]+s+r
else:
	ans=r[::-1]+s[::-1]+l

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

s=list(input())
n1=len(s)

import sys
sys.setrecursionlimit(10**9)

def a(s,n1):
    for i in range(1,len(s)):
        if s[i-1]=="0" and s[i]=="1" or s[i-1]=="1" and s[i]=="0":
            s[i-1]=s[i]="a"
    s=list("".join(s).replace("a",""))
    
    if len(set(s))==1 or s==[]:
        print(n1-len(s))
    else:
        a(s,n1)
a(s,n1)    


### FIXED CODE ###

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

cnt=0

if b//a >c:
    print(c)
else:
    print(b//a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

N, K = map(int, input().split())
A = [int(i) for i in input().split()]
    
def func():
    for i in range(1, K+1):
        for j in range(N):
            if i - A[j] >= 0:
                dp[i] |= ~dp[i - A[j]]
                
dp = [0 for i in range(K+1)]
func()
if dp[K]: print("First")
else: print("Second")

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

dp = [0 for i in range(K+1)]
for i in range(K+1):
    if not dp[i]:
        for j in range(N):
            if i + A[j] < K + 1:
                dp[i+A[j]] = 1

if dp[K]: print("First")
else: print("Second")
### BUGGY CODE ###

n, m, Q = map(int, input().split())
lr = [[0] * n for i in range(n)]
for _ in range(m):
  l, r = map(int, input().split())
  lr[l-1][r-1] += 1
pq = [list(map(int, input().split())) for _ in range(Q)]
for i in pq:
  p = i[0]
  q = i[1]
  ans = 0
  for j in range(p-1, q):
    for k in range(p-1, q):
      ans += lr[j][k]
  print(ans)

### FIXED CODE ###

def getSumRange(L, R):
    ans = sum[R][R] - sum[R][L - 1] - sum[L - 1][R] + sum[L - 1][L - 1]
    return ans

n, m, Q = map(int, input().split())
L = [0] * m
R = [0] * m
for i in range(m):
    L[i], R[i] = map(int, input().split())
p = [0] * Q
q = [0] * Q
for i in range(Q):
    p[i], q[i] = map(int, input().split())

sum = [[0] * (n + 1) for i in range(n + 1)]
for i in range(m):
    sum[L[i]][R[i]] += 1
for i in range(n + 1):
    for j in range(n + 1):
        sum[i][j] += sum[i - 1][j]
        sum[i][j] += sum[i][j - 1]
        sum[i][j] -= sum[i - 1][j - 1]

for i in range(Q):
    ans = getSumRange(p[i], q[i])
    print(ans)
### BUGGY CODE ###

def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            dp[i+k] = min(dp[i+k],dp[i]+abs(H[i+k]-H[i]))
    ans = dp[-1]
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examB()

"""

"""

### FIXED CODE ###

N,K = map(int, input().split())
h = list(map(int, input().split()))
dp = [0]*N
ans = int(0)
c = int(0)
if N < K:
    c = N-1
else:
    c = K
for i in range(c):
    dp[i+1] = abs(h[i+1]-h[0])

for i in range(2,N):
    if i<K:
        c = i
    else:
        c = K
    dpcandi = [0] * c
    for j in range(c):
        dpcandi[j] = dp[i-j-1] + abs(h[i]-h[i-j-1])
    dp[i] = min(dpcandi)

ans = dp[N-1]

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

N = int(input())
members = list(map(int, input().split()))
junban = []

for i in range(1, N+1):
  junban.append(members.index(i)+1)
  
for i in junban:
  print(i,end=' ')

### FIXED CODE ###

N = int(input())
members = list(map(int, input().split()))
junban = {}

for i,member in zip(range(N), members):
  junban[member] = i+1
  
for i in junban.values():
  print(i,end=' ')
### BUGGY CODE ###

s=input()
ans=0
while(1):
    for i in range(1,len(s)-1):
        if s[i-1]=="A" and s[i]=="B" and s[i+1]=="C":
            ans+=1
            s=s[:i-1]+"BCA"+s[i+2:]

    if not "ABC" in s:
        print(ans)
        exit()

### FIXED CODE ###

s=input().replace("BC","X")
ans=0
acc=0
for i in range(len(s)):
    if s[i]=="B" or s[i]=="C":
        acc=0

    elif s[i]=="A":
        acc+=1
    elif s[i]=="X":
        ans+=acc


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

n=int(input())
a=list(map(int,input().split()))
c=0
for i in range(n):
  for j in range(i,n):
    if sum(a[i:j+1])==0:c+=1
print(c)

### FIXED CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
c=0
l=[0]
for i in range(n):
  l.append(l[i]+a[i])
L=collections.Counter(l)
for j in L.values():
  c+=int(j*(j-1)/2)
print(c)
### BUGGY CODE ###

from fractions import gcd
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        A, B = map(int, input().split())

        _gcd = gcd(A, B)

        root_gcd = _gcd ** 0.5
        p = 2
        prim_num = 1
        while p <= root_gcd or _gcd > 1:
            tmp = _gcd
            while True:
                if _gcd % p == 0:
                    _gcd /= p
                else:
                    break
            if tmp != _gcd:
                prim_num += 1

            p += 1
        print(prim_num)


# Run main
if __name__ == '__main__':
    AtCoder().main()


### FIXED CODE ###

import sys

input = sys.stdin.readline


class AtCoder:

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

    def factorize(self, n):
        p = 2
        res = 1
        while p * p < n:
            if n % p == 0:
                res += 1
                while n % p == 0:
                    n /= p
            p += 1
        if n != 1:
            res += 1
        return res

    def main(self):
        A, B = map(int, input().split())

        _gcd = self.gcd(A, B)
        print(self.factorize(_gcd))


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

N, M = (int(x) for x in input().split())
L, R = [None]*M, [None]*M
for i in range(M):
    L[i], R[i] = (int(x) for x in input().split())

tmp = set(range(L[0], R[0]+1))
for j in range(1, M):
    tmp = tmp & set(range(L[j], R[j]+1))

print(len(tmp))


### FIXED CODE ###

N, M = (int(x) for x in input().split())
L, R = [None]*M, [None]*M
for i in range(M):
    L[i], R[i] = (int(x) for x in input().split())

tmp = [L[0], R[0]]
for j in range(1, M):
    if tmp[0] < L[j]:
        tmp[0] = L[j]
    if R[j] < tmp[1]:
        tmp[1] = R[j]
    if tmp[0] > tmp[1]:
        print(0)
        exit()

print(tmp[1]-tmp[0]+1)
### BUGGY CODE ###

import math

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

def combinations_count(s, r):
    return math.factorial(s) // (math.factorial(s - r) * math.factorial(r))

p = combinations_count(n, a)
q = combinations_count(n, b)

print(2**n-1-p-q)

### FIXED CODE ###

N,a,b=map(int,input().split())
m = 10**9+7

M = pow(2, N, m)

def nCr(n,r):
    if r*2>n:
        return nCr(n,n-r)
    else:
        a = b = 1
        for i in range(r):
            a = a * (n - i) % m
            b = b * (r - i) % m
        return (a * pow(b,m-2,m)) % m
 
ans = M - 1 - nCr(N,a) - nCr(N,b)
print(ans%m)
### BUGGY CODE ###

from heapq import heapify, heappop, heappush
INF = 1e7

H,W=map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

S = [input() for _ in range(H)]

D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
def dijkstra(sx, sy):
    # Color = [[0]*(W) for _ in range(H)] # 0: 未訪問 1: Seen 2: Visited
    # P = [None]*N #親

    D[sx][sy] = 0
    # P[s] = None
    # PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。
    PQ = [(0, sx, sy)]
    heapify(PQ)
    while PQ: # PQに候補がある限り
        min_cost, ux, uy = heappop(PQ) # 最小コストなノードu
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                xx, yy = ux+dx, uy+dy
                if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                    is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                    # neighborでなければコストが1増える
                    if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                        D[xx][yy] = D[ux][uy] + is_not_neighbor
                        heappush(PQ, (D[xx][yy], xx, yy))
    

dijkstra(ch-1, cw-1)
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

### FIXED CODE ###

import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, (sx, sy))]
heapq.heapify(PQ)
while PQ: # PQに候補がある限り
    _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
A = list(set(a))
c = 0
ac = 0
for i in range(len(A)):
    ac = a.count(A[i])
    if ac >= A[i]:
        c += ac - A[i]
    elif ac > 0:
        c += ac
print(c)


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
if N == 1:
    if a[0] != 1:
        print(1)
        exit()
    else:
        print(0)
        exit()
a.sort()
A = 0
c = 0
while True:
    try:
        #print(a)
        A = a[0]
        if len(a)>1:
            for i in range(1, len(a)):
                if a[i] != A:
                    # print(i + 1)
                    # c += i
                    del a[:i]
                    if i >= A:
                        c += i - A
                    else:
                        c += i
                    # print(a[i], c)
                    break
                elif i == len(a) - 1:
                    if i + 1 >= A:
                        c += i + 1 - A
                    else:
                        c += i + 1
                    print(c)
                    exit()
        else:
            print(c + 1)
            exit()
    except IndexError:
        break
### BUGGY CODE ###

N = int(input())
nu = [int(x) for x in input().split()]
r2 = {}

for i in nu:
  r2[i] = nu.index(i)
#print(r2)

j2 = []
for i in range(len(r2)):
  j2.append(r2[i+1]+1)
#print(j2)

print(" ".join([str(x) for x in j2]))

### FIXED CODE ###

from sys import stdin
import numpy as np


# noinspection PyShadowingBuiltinsInspection

def main():
    n = int(input())
    students = [int(x) for x in input().split()]
    ret = [0] * n
    for i in range(n):
        ret[students[i] - 1] = i + 1
    print(" ".join([str(x) for x in ret]))
    return


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

# coding: utf-8

N, W = map(int, input().split())
   
dp = [-1] * (W+1)
dp[0] = 0

for i in range(1, N+1):
    w, v = map(int, input().split())
    for j in range(W-w, -1, -1):
        if dp[j] == -1:
            continue
        if dp[j+w] < dp[j]+v:
            dp[j+w] = dp[j] + v

# for i in range(N+1):
#     print(dp[i])

print(max(dp))

### FIXED CODE ###

def main():
    N, W = map(int, input().split())
 
    dp = [-1] * (W + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v
    print(max(dp))
 
 
main()
### BUGGY CODE ###

R, C, K = map(int, input().split())
D = dict()
for _ in range(K):
    r, c, v = map(int, input().split())
    D[(r, c)] = v

dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
for r in range(1, R + 1):
    for c in range(1, C + 1):
        m = max(dp[i][r - 1][c] for i in range(4))
        for n in range(4):
            dp[n][r][c] = max(m, dp[n][r][c - 1])
        if (r, c) in D:
            for n in range(3):
                dp[n + 1][r][c] = max(dp[n + 1][r][c],
                                      m + D[(r, c)],
                                      dp[n][r][c - 1] + D[(r, c)])
print(max(dp[i][-1][-1] for i in range(4)))


### FIXED CODE ###

import sys

input = sys.stdin.readline

R, C, K = map(int, input().split())
D = dict()
for _ in range(K):
    r, c, v = map(int, input().split())
    D[(r, c)] = v

dp0 = [[0] * (C + 1) for _ in range(R + 1)]
dp1 = [[0] * (C + 1) for _ in range(R + 1)]
dp2 = [[0] * (C + 1) for _ in range(R + 1)]
dp3 = [[0] * (C + 1) for _ in range(R + 1)]

for r in range(1, R + 1):
    for c in range(1, C + 1):
        m = max(dp0[r - 1][c], dp1[r - 1][c], dp2[r - 1][c], dp3[r - 1][c])
        dp0[r][c] = max(m, dp0[r][c - 1])
        dp1[r][c] = max(m, dp1[r][c - 1])
        dp2[r][c] = max(m, dp2[r][c - 1])
        dp3[r][c] = max(m, dp3[r][c - 1])
        if (r, c) in D:
            dp1[r][c] = max(dp1[r][c], m + D[(r, c)], dp0[r][c - 1] + D[(r, c)])
            dp2[r][c] = max(dp2[r][c], m + D[(r, c)], dp1[r][c - 1] + D[(r, c)])
            dp3[r][c] = max(dp3[r][c], m + D[(r, c)], dp2[r][c - 1] + D[(r, c)])
print(max(dp0[-1][-1], dp1[-1][-1], dp2[-1][-1], dp3[-1][-1]))
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]

a.sort()
bc.sort(key=lambda x: x[1], reverse=True)
d = []
i = 0

while len(d) <= n and i < len(bc):
    d += ([bc[i][1]] * bc[i][0])
    i += 1

if len(d) > n:
    d = d[:n]

sum_max = sum(a)
for x in range(len(d)):
    a[x] = d[x]
    sum_a = sum(a)
    if sum_a > sum_max:
        sum_max = sum_a

print(sum_max)


### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]

bc.sort(key=lambda x: x[1], reverse=True)
d = []
i = 0

while len(d) <= n and i < len(bc):
    d += ([bc[i][1]] * bc[i][0])
    i += 1

if len(d) > n:
    d = d[:n]

a += d
a.sort(reverse=True)

print(sum(a[:n]))