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

import numpy as np

def resolve():
    n, w = map(int, input().split())
    goods = np.array([list(map(int, input().split())) for _ in range(n)])

    dp = np.zeros(1)
    print(knapsack(n - 1, w, goods, dp))



def knapsack(i, j, goods, dp):
    """残りi個の品物から、重さがj以下になるように選んだときの価値の最大値をreturnする関数"""
    if i < 0:
        # もう品物は残っていない
        return 0
    if j < goods[i][0]:
        # 品物が重すぎて入らない
        return knapsack(i - 1, j, goods, dp)
    else:
        # 品物を入れる場合と入れない場合とで、価値が大きい方をreturn 
        return max(knapsack(i - 1, j - goods[i][0], goods, dp) + goods[i][1], knapsack(i - 1, j, goods, dp))

resolve()

### FIXED CODE ###

def resolve():
    n, w = map(int, input().split())
    goods = [list(map(int, input().split())) for _ in range(n)]

    dp = [[0] * (w + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in reversed(range(w + 1)):
            # もしi番目の品物が入るのであれば
            if goods[i - 1][0] <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - goods[i - 1][0]] + goods[i - 1][1])
            else:
                dp[i][j] = dp[i - 1][j]

    print(dp[n][w])
    
resolve()
### BUGGY CODE ###

n = int(input())
mul = 1
lst = list(map(int,input().split()))
for ele in lst:
  mul = mul *ele
if(mul > 1e18):
  print(-1)
else:
  print(mul)


### FIXED CODE ###

def solve():
    n = int(input())
    lst = list(map(int,input().split()))
    if 0 in lst:
        print(0)
        return
    mul = 1
    for ele in lst:
        mul = mul * ele
        if mul > 1e18:
            print(-1)
            return
    
    print(mul)
    
solve()
### BUGGY CODE ###

s = input()
k = int(input())
l = len(s)
sub = [s]
for i in range(0,l):
    for j in range(1,l):
        sub.append(s[i:i+j])
sub = set(sub)
print(sorted(sub)[k-1])

### FIXED CODE ###

s = input()
k = int(input())
l = len(s)
sub = set()
for i in range(l):
    for j in range(1,k+1):
        sub.add(s[i:i+j])
print(sorted(sub)[k-1])
### BUGGY CODE ###

N, Q = map(int, input().split())
rela = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    rela[a].append(b)
    rela[b].append(a)
    cnt = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    cnt[p - 1] += x
from collections import deque
que = deque([[-1, 0]])
while que:
    par, cur = que.popleft()
    for new in rela[cur]: 
        if new == par:
            continue
        cnt[new] += cnt[cur]
        que.append([cur, new])
print(*cnt)


### FIXED CODE ###

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion
n, q = map(int, input().split())

tree_index = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  tree_index[a].append(b) # a<bとは限らないため、双方向にする
  tree_index[b].append(a)
ans = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
def dfs(cur, par):
    for chl in tree_index[cur]:
      if chl == par: #parentとchildが等しい時はスキップ
        continue
      ans[chl] += ans[cur] 
      dfs(chl, cur)
dfs(0, -1)
print(*ans)
### BUGGY CODE ###

l,r=map(int,input().split())
min = 2018
for i in range(l,r,1):
  for j in range(i+1,r+1,1):
    if (i*j)%2019 < min:
      min = (i*j)%2019
      if min == 0:
        break

print(min)

### FIXED CODE ###

L,R=map(int,input().split())
if R-L>2019:
  print(0)
elif L%2019==0 or R%2019==0:
  print(0)
elif L//2019!=R//2019:
  print(0)
else:
  L=L%2019
  R=R%2019
  ans=2019
  for i in range(L,R):
    for j in range(i+1,R+1):
      ans=min(ans,(i*j)%2019)
      if ans==0:
        break

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

N = int(input())
A = []
for i in range(N):
    temp = list(map(int, input().split()))
    for j in range(N-1):
        temp[j] -= 1
    A.append(temp)

cur = [0] * N
goal = 0
day = 0
while goal < N:
    day += 1
    changed = False
    new_cur = cur[:]
    for i in range(N):
        if cur[i] == N-1:
            continue
        opponent =  A[i][cur[i]]
        if A[opponent][cur[opponent]] == i:
            new_cur[i] += 1
            changed = True
            if new_cur[i] == N-1:
                goal += 1
    cur = new_cur
    if not changed:
        print(-1)
        exit()

print(day)


### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    temp = list(map(int, input().split()))
    for j in range(N-1):
        temp[j] -= 1
    A.append(temp)

cand = list(range(N))
cur = [0] * N
goal = 0
day = 0
while goal < N:
    day += 1
    game = []
    new_cur = cur[:]
    for i in cand:
        if i in game or cur[i] == N-1:
            continue
        opponent = A[i][cur[i]]
        if A[opponent][cur[opponent]] == i:
            new_cur[i] += 1
            new_cur[opponent] += 1
            game.append(i)
            game.append(opponent)
            if new_cur[i] == N-1:
                goal += 1
            if new_cur[opponent] == N-1:
                goal += 1
    cand = game
    cur = new_cur
    if not game:
        print(-1)
        exit()

print(day)
### BUGGY CODE ###

N = int(input())

mod = 0
for i in range(1,N):
    M = i%(i+1)
    mod += M
print(mod)


### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

n=int(input())
S=input()

def e():
    for l in range(n//2, 0, -1):
        for i in range(n-l+1):
            if n-(l+i)<l:
                break
            s=S[i:i+l]
            if len(S.split(s))>=3:
                return l
    return 0


print(e())

### FIXED CODE ###

N = int(input())
S = input()

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

ans = 0

for j in range(N - 1, 0, -1):
    sj = S[j]
    for i in range(j-1, -1, -1):
        si = S[i]
        if j == N - 1:
            if si == sj:
                dp[j][i] = 1
                ans = 1
        else:
            if si == sj:
                dp[j][i] = min(j - i, dp[j + 1][i + 1] + 1)
                ans = max(ans, dp[j][i])

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

n = int(input())
s = input()

min_ = n
for i in range(n):
  temp = s[:i].count("W") + s[i+1:].count("E")
  min_ = min(temp, min_)
print(min_)

### FIXED CODE ###

n = int(input())
s = input()

min_ = n
A = [0] * n
for i in range(n):
  if s[i] == "W":
    A[i] = A[i-1] + 1
  else:
    A[i] = A[i-1]

val = (n-1 - (A[-1] - A[0]))
min_ = min(min_, val)
for i in range(1, n):
  val = A[i-1] + (n-1 - i - (A[-1] - A[i]))
  min_ = min(val, min_)
print(min_)
### BUGGY CODE ###

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1
while ba-fr > 1:
    mi = (ba+fr+1) // 2
    x = a[mi-1]
    if x >= k:
        ba = mi
        continue
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    #print(dp)
    if sum(dp[k-x:k]):
        ba = mi
    else:
        fr = mi

print(fr)

### FIXED CODE ###

import sys

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if check(1):
    print(0)
    sys.exit()

if not check(n):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)
### BUGGY CODE ###

from collections import defaultdict

n = int(input())
d = []
count = 0
for _ in range(n):
    s = input()
    dic = defaultdict(int)
    for c in s:
        dic[c] += 1
    for i in range(len(d)):
        if all(dic[key] == d[i][key] for key in dic):
            count += 1
    d.append(dic)


print(count)


### FIXED CODE ###

import collections

n = int(input())
S = []
count = 0
for _ in range(n):
    S.append(''.join(sorted(list(input()))))

for i, v in collections.Counter(S).items():
    for i in range(1, v):
        count += i

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

import numpy as np
s = np.array(list(input()))
n = len(s)
ans = 0
i = 0
while i < n-2:  # 3文字なので
    if s[i] == 'A' and s[i+1] == 'B' and s[i+2] == 'C':
        s[i:i+3] = ['B', 'C', 'A']
        ans += 1
        i = max(i-1, 0)   # 1つ前がAの場合をチェック
    else:
        i += 1

print(ans)

### FIXED CODE ###

s = input()
n = len(s)
ans = 0
numa = 0
i = 0
while i < n-1:  # 最後'BC'以外は、最後の文字は関係ないので s[n-1]は不要
    if s[i] == 'A':
        numa += 1   # Aが連続で続く場合は数える
    elif s[i:i+2] == 'BC':
        ans += numa # AAAA と BC を入れ替える回数。またBCが来たら加算する
        i += 1  # BCの場合は、2文字進めるので+1
    else:
        numa = 0
    i += 1
print(ans)
### BUGGY CODE ###

from collections import defaultdict
from functools import reduce

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

MOD = 10 ** 9 + 7

def mul(a, b):
  return ((a % MOD) * (b % MOD)) % MOD

def power(x, y):
  if y == 0:
    return 1
  elif y == 1:
    return x % MOD
  elif y % 2 == 0:
    return power(x, y // 2) ** 2 % MOD
  else:
    return mul(power(x, y // 2) ** 2, x)

def div(a, b):
  return mul(a, power(b, MOD - 2))

numer_cache = defaultdict(dict)
denom_inv_cache = {}

def numer(n, r):
  if r == 0:
    return 1
  if r not in numer_cache[n]:
    numer_cache[n][r] = mul(numer(n, r - 1), n - r + 1)
  return numer_cache[n][r]

def denom_inv(r):
  if r == 0:
    return 1
  if r not in denom_inv_cache:
    denom_inv_cache[r] = div(denom_inv(r - 1), r)
  return denom_inv_cache[r]

def combinations_count(n, r):
  r = min(r, n - r)
  return mul(numer(n, r), denom_inv(r))

print(sum(mul(combinations_count(n, i), combinations_count(n - 1, i)) for i in range(min(n, k + 1))) % MOD)


### FIXED CODE ###

from collections import defaultdict
from functools import reduce

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

MOD = 10 ** 9 + 7

def mul(a, b):
  return a * b % MOD

def power(x, y):
  res = 1
  while True:
    if y & 1:
      res = res * x % MOD
    if y == 1:
      return res
    x = x * x % MOD
    y >>= 1

def div(a, b):
  return a * power(b, MOD - 2) % MOD

def dict1():
  return {0: 1}

numer_cache = defaultdict(dict1)
denom_inv_cache = dict1()

def combinations_count(n, r):
  r = min(r, n - r)
  numer_cache_n = numer_cache[n]
  if r not in numer_cache_n:
    numer_cache_n[r] = mul(numer_cache_n[r - 1], n - r + 1)
  if r not in denom_inv_cache:
    denom_inv_cache[r] = div(denom_inv_cache[r - 1], r)
  return mul(numer_cache_n[r], denom_inv_cache[r])

print(sum(mul(combinations_count(n, i), combinations_count(n - 1, i)) for i in range(min(n, k + 1))) % MOD)
### BUGGY CODE ###

import sys
n,k = list(map(int,sys.stdin.readline().split()))
arr = list(map(int,sys.stdin.readline().split()))

dp = [sys.maxsize for i in range(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(arr[i]-arr[j]))
sys.stdout.write(str(dp[-1])+'\n')

### FIXED CODE ###

import sys
n,k = list(map(int,input().split()))
arr = list(map(int,input().split()))

dp = [sys.maxsize for i in range(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(arr[i]-arr[j]))
print(dp[-1])
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

from copy import deepcopy

def main():
  n = int(input())  
  la = sorted([int(input()) for _ in range(n)])
  
  lo = deepcopy(la)
  ind = 0
  def f(la, ind):
    lx = []
    while len(la) > 0:
      lx.append(la.pop(ind))
      ind = -1 if ind == 0 else 0
    ls = sorted([abs(lx[i] - lx[i-1]) for i in range(len(lx))])
    return sum(ls[1:])
  print(max(f(deepcopy(la), 0), f(deepcopy(la), -1)))

  
if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

from copy import deepcopy

def main():
  n = int(input())  
  la = sorted([int(input()) for _ in range(n)])
  
  lo = deepcopy(la)
  ind = 0
  def f(la, ind):
    lx = []
    while len(la) > 0:
      lx.append(la.pop(ind))
      ind = -1 if ind == 0 else 0
    ls = ([abs(lx[i] - lx[i-1]) for i in range(len(lx))])
    return sum(ls)-min(ls)
  print(max(f(deepcopy(la), 0), f(deepcopy(la), -1)))

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

r, g, b, n = map(int, input().split())

cnt = 0
for i in range(3001):
    for j in range(3001):
        x = n - (r * i + g * j)
        if x < 0:
            continue
        if x % b == 0:
            cnt += 1

print(cnt)


### FIXED CODE ###

r, g, b, n = map(int, input().split())

cnt = 0
for i in range(int(n//r)+1):
    r_num = r * i
    for j in range(int((n - r_num)//g)+1):
        g_num = g * j
        b_num = (n - r_num - g_num)
        if b_num >= 0 and b_num % b == 0:
            cnt += 1

print(cnt)
### BUGGY CODE ###

N = int(input())
ans=1
for i in range(1,N+1):
    ans*=i
print(ans%(10**9+7))

### FIXED CODE ###

def factorial(N):
    a = 1
    for n in range(2,N+1):
        a = a*n % (10**9 + 7)
    return a
 
if __name__ == '__main__':
    N = int(input())
    print(factorial(N))
### BUGGY CODE ###

N = int(input())
dic = [[-1]*(N+1) for _ in range(N+1)]
M = [[] for _ in range(N+1)]
used = [-1]*(N+1) 
for i in range(N-1):
    u,v,w = map(int,input().split())
    M[u-1].append([v-1,w])
    M[v-1].append([u-1,w])


from collections import deque 
q = deque()
q.append([0,0])
used[0] = 0
# print(M)
while q:
    # print(q)
    e,c = q.pop()
    for i,d in M[e]:
        if used[i]==-1:
            C = (c+d)%2
            used[i] = C
            q.append([i,C])  
for i in used[:-1]:
    print(i)


### FIXED CODE ###

n = int(input())
from collections import deque
#隣接リストedge
edge = [[] for i in range(n)]
d = [-1] * n
#入力
for i in range(n-1):
    x,y,cost = map(int,input().split())
    #edge[x].append([cost,y])
    #edge[y].append([cost,x])
    x -=1
    y -=1
    cost %=2
    edge[x].append((cost,y))
    edge[y].append((cost,x))
q = deque()
q.append(0)
d[0] =0
while q:
    t = q.popleft()
    for s in edge[t]:
        if d[s[1]] == -1:
            d[s[1]] = d[t] + s[0]
            q.append(s[1])
for i in d:
    print(i%2)
### BUGGY CODE ###

k = int(input())

def mygcd(x,y):
    a = min(x,y)  # 最小値
    b = max(x,y)  # 最大値
    q = 2  # 商
    r = 2  # 余り
    while r != 0:
        q = b / a
        r = b % a
        b = a
        a = r
    return b

ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans += mygcd(mygcd(i,j),k)

print(ans)

### FIXED CODE ###

K   = int(input())
Sum = 0
def mygcd(x,y):
    a = min(x,y)  # 最小値
    b = max(x,y)  # 最大値
    r = 2  # 余り
    while r != 0:
        r = b % a
        b = a
        a = r
    return b

for A in range(1,K+1):
    for B in range(1,K+1):
        AB = mygcd(A,B)
        if AB==1:
            Sum = Sum+K
        else:
            for C in range(1,K+1):
                Sum = Sum+mygcd(AB,C)
print(Sum)
### BUGGY CODE ###

import  itertools

n,p=map(int,input().split())
a=list(map(int,input().split()))
ans=0
nums=[0,1]


def judge(C):
    er=0
    for i,cnt in enumerate (C):
        if cnt==1:
            er+=a[i]
    if er%2==p:
        return True
    else:
        return False


for biscuits in itertools.product(nums,repeat=n):
    t=list(biscuits)
    if judge(t):
        ans+=1

print(ans)

### FIXED CODE ###

n,p=map(int,input().split())
a=list(map(int,input().split()))
odd=[0]*n
even=[0]*n

if a[0]%2==0:
    even[0]=2
else:
    odd[0]=1
    even[0] = 1

for i in range(n-1):
    if a[i+1]%2==0:
        odd[i+1]+=odd[i]*2
        even[i+1]+=even[i]*2
    else:
        odd[i+1]+=even[i]+odd[i]
        even[i+1]+=odd[i]+even[i]

if p==0:
    print(even[n-1])
else:
    print(odd[n-1])
### BUGGY CODE ###

def main():
    from bisect import bisect_left as bl
    from bisect import bisect_right as br

    def b_search(ok, ng, value):
        while abs(ok-ng) > 1:
            mid = (ok+ng)//2
            if value(mid):
                ok = mid
            else:
                ng = mid
        return ok

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

    inf = 10**18+1

    def check(x):
        cnt = 0
        for i in a:
            if i < 0:
                if x % i == 0:
                    cnt += n - br(a, x//i)
                else:
                    cnt += n - br(a, x//i + 0.1)
            elif i > 0:
                if x % i == 0:
                    cnt += bl(a, x//i)
                else:
                    cnt += bl(a, x//i + 0.1)
            else:
                if x > 0:
                    cnt += n
                else:
                    cnt += 0
        for i in a:
            if i*i < x:
                cnt -= 1
        return cnt//2 < k

    print(b_search(-inf, inf, check))


main()


### FIXED CODE ###

def main():
    from bisect import bisect_left as bl

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

    inf = 10**18+1

    ok = -inf
    ng = inf
    start_0 = bl(a, 0)
    start_1 = bl(a, 1)

    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        cnt = 0
        if mid >= 0:
            now = 0
            if start_0 > 0:
                for i in a[start_0-1::-1]:
                    while now < n:
                        if i*a[now] >= mid:
                            now += 1
                        else:
                            break
                    cnt += n - now
            now = n
            for i in a[start_1:]:
                while now > 0:
                    if i*a[now-1] >= mid:
                        now -= 1
                    else:
                        break
                cnt += now
        else:
            now = 0
            for i in a[:start_0]:
                while now < n:
                    if i*a[now] >= mid:
                        now += 1
                    else:
                        break
                cnt += n - now
            now = n
            for i in a[n-1:start_1-1:-1]:
                while now > 0:
                    if i*a[now-1] >= mid:
                        now -= 1
                    else:
                        break
                cnt += now
        if mid > 0:
            cnt += n * (start_1 - start_0)
        cnt -= len([None for i in a if i*i < mid])
        if cnt//2 < k:
            ok = mid
        else:
            ng = mid
    print(ok)


main()
### BUGGY CODE ###

import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
MOD = pow(10,9)+7
N = int(input())
d = [[N,0] for _ in range(60)]
A = list(map(int,input().split()))
for k in A:
    c = 0
    while k > 0:
        if k % 2 == 1:
            d[c][0] -= 1
            d[c][1] += 1
        k = k // 2
        c += 1
s = 0
for i in range(60):
    li = d[i]
    s += (li[0]*li[1]*pow(2,i,MOD))%MOD
print(s%MOD)

### FIXED CODE ###

import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
from collections import defaultdict
MOD = pow(10,9)+7
N = int(input())
d = [[N,0] for _ in range(60)]
A = list(map(int,input().split()))
for k in A:
    c = 0
    while k > 0:
        if k % 2 == 1:
            d[c][0] -= 1
            d[c][1] += 1
        k = k // 2
        c += 1
s = 0
for i in range(60):
    li = d[i]
    s += (li[0]*li[1]*pow(2,i,MOD))%MOD
print(s%MOD)
### BUGGY CODE ###

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

ans = 1
for i in a:
  ans *= i
  if ans == 0:
    print(0)
    exit()
if ans > 10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

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

if 0 in a:
    print(0)
    exit()
    
ans = 1
for i in range(n):
    ans *= a[i]
    if ans > 10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

K = int(input())

if K%2 == 0:
    print(-1)

suretu = 7
i = 1
for i in range(10**7 + 9):
    if suretu%K == 0:
        print(i+1)
        break
    else:
        i += 1
        suretu *= 10
        suretu += 7

### FIXED CODE ###

K = int(input())
remainder_set = set()
sequence = 7
i = 1
for i in range(K):
    remainder = sequence%K
    #print(sequence,remainder)
    if remainder == 0:
        print(i+1)
        break
    else:
        if remainder in remainder_set:
            print(-1)
            break
        else:
            i += 1
            remainder_set.add(remainder)
            sequence = remainder*10 + 7
### BUGGY CODE ###

from collections import defaultdict
s, t = [x.strip() for x in open(0).readlines()]
if set(t) - set(s) != set():
    print(-1)
else:
    d = defaultdict(list)
    n = len(s)
    for i, c in enumerate(s, 1):
        d[c].append(i)
    for k in d:
        d[k].append(d[k][0] + n)
    ans = 0
    d
    for c in t:
        q, r = divmod(ans, n)
        for x in d[c]:
            if r < x:
                ans = n*q + x
                break
    print(ans)

### FIXED CODE ###

from collections import defaultdict
import bisect
s, t = [x.strip() for x in open(0).readlines()]
if set(t) - set(s) != set():
    print(-1)
else:
    d = defaultdict(list)
    n = len(s)
    for i, c in enumerate(s, 1):
        d[c].append(i)
    for k in d:
        d[k].append(d[k][0] + n)
    ans = 0
    for c in t:
        q, r = divmod(ans, n)
        x = d[c][bisect.bisect(d[c], r)]
        ans = n*q + x
    print(ans)
### BUGGY CODE ###

N = int(input())
count_dict = {}
s = [''.join(sorted(input())) for i in range(N)]
for word in s:
    if word in list(count_dict.keys()):
        count_dict[word] +=1
    else:
        count_dict[word] = 1
result = sum([i *(i-1)/2 for i in count_dict.values()])
print(int(result))

### FIXED CODE ###

N = int(input())
d = dict()
for i in range(N):
    S = input()
    S = ''.join(sorted(list(S)))
    if S in d.keys():
        d[S] += 1
    else:
        d[S] = 1

ans = 0
for n in d.values():
    ans += n*(n-1)//2
print(ans)
### BUGGY CODE ###

def main():
	n, m = map(int, input().split())
	a = list(map(int, input().split()))
	for _ in range(m):
		b, c = map(int, input().split())
		a += [c]*b
	a.sort()
	print(sum(a[::-1][:n]))
	return
main()

### FIXED CODE ###

def main():
	n, m = map(int, input().split())
	a = list(map(int, input().split()))
	dic = {}
	lst = []
	for i in a:
		if i in dic:
			dic[i] = dic[i] + 1
		else:
			lst += [i]
			dic[i] = 1
	for _ in range(m):
		b, c = map(int, input().split())
		if c in dic:
			dic[c] = dic[c] + b
		else:
			dic[c] = b
			lst += [c]
	lst.sort()
	lst = lst[::-1]
	i = 0
	ans = 0
	while n>0:
		ans += lst[i]*min(dic[lst[i]], n)
		n -= dic[lst[i]]
		i += 1
	print(ans)
	return
main()