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

from functools import reduce
n = int(input())
s = []
count = 0
for _ in range(n):
    s.append(sorted(input()))
    s[_] = ''.join(s[_]).rstrip('\n')
set_s = set(s)
for i in range(len(set_s)):
    s_count = s.count(list(set_s)[i])
    count += s_count * (s_count - 1) // 2
print(count)

### FIXED CODE ###

n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
count = {}
ans = 0
for i in s:
    count[i] = count.get(i, 0) + 1
for key, value in count.items():
    ans += value * (value - 1) // 2
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
ans=sum(a)
l=[]
for i in range(m):
    b,c=map(int,input().split())
    l.append((b,c))
l.sort(key=lambda x:x[1],reverse=True)
x=[]
for i in range(m):
    xx=[l[i][1]]*l[i][0]
    x.extend(xx)
c=0
while a[c]<x[c] :
    ans+=x[c]-a[c]
    c+=1
    if c>=len(a) or c>=len(x):
        break
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
l=[]
for i in range(n):
    l.append([1,a[i]])
for i in range(m):
    l.append(list(map(int,input().split())))
l.sort(key=lambda x:x[1], reverse=True)
c=0
ans=0
for i in range(n+m):
    ans+=l[i][1]*l[i][0]
    c+=l[i][0]
    if c>n:
        ans-=l[i][1]*(c-n)
        break
print(ans)
### BUGGY CODE ###

#ABC 103
#最小公倍数
from functools import reduce

#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#a,bの最小公倍数
def lcm_base(a, b):
    return a * b // gcd (a, b)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
N=int(input())
A = [int(j) for j in input().split()]

ans = 0
for a in A:
    ans+=(lcm(*A)-1)%a
print(ans)

### FIXED CODE ###

#ABC 103
N=int(input())
A = [int(j) for j in input().split()]
print(sum(A)-len(A))
### BUGGY CODE ###

N = int(input())

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

ans = 1
for i in A:
    ans *= i

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())

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

flag = True
ans = 1
if 0 in A:
    print(0)
    flag = False

if flag:
    for i in A:
        ans *= i
        if ans > pow(10,18):
            print(-1)
            flag = False
            break

if flag:
    print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(n):
    for j in range(max(i + 1, a[i] + 1), n):
        if abs(i - j) == a[i] + a[j]:
            ans += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
ap = defaultdict(int)
for i in range(n):
    ap[i - a[i]] += 1

ans = 0
for i in range(n):
    ans += ap[a[i] + i]
print(ans)
### BUGGY CODE ###

# coding: utf-8

N, M = (int(x) for x in input().split())

pass_ids = [x for x in range(N)]
for i in range(M):
	L, R = (int(x) - 1 for x in input().split())
	pass_ids = [x for x in pass_ids if L <= x <= R]

print(len(pass_ids))

### FIXED CODE ###

# coding: utf-8

N, M = (int(x) for x in input().split())

pass_ids = [x for x in range(N)]

L_max, R_min = 0, N
for i in range(M):
	L, R = (int(x) - 1 for x in input().split())
	
	if L_max < L:
		L_max = L
	if R_min > R:
		R_min = R


if L_max < R_min + 1:
	print(len(list(range(L_max, R_min + 1))))
else:
	print("0")
### BUGGY CODE ###

n = int(input())
line = list(input())
cum_sum_w = [0]
cum_sum_e = [0]
for i in range(n):
    cum_sum_w.append(line[:i + 1].count('W'))
    cum_sum_e.append(line[:i + 1].count('E'))
count_list = []
for i in range(n):
    count = 0
    count += cum_sum_w[i]
    count += cum_sum_e[n] - cum_sum_e[i]
    count_list.append(count)
print(min(count_list))


### FIXED CODE ###

n = int(input())
line = list(input())
cum_sum_w = [0]
cum_sum_e = [0]
count_w = 0
count_e = 0
for i in range(n):
    if line[i] == 'W':
        count_w += 1
    else:
        count_e += 1
    cum_sum_w.append(count_w)
    cum_sum_e.append(count_e)
count_list = []
for i in range(1, n + 1):
    count = 0
    count += cum_sum_w[i - 1]
    count += cum_sum_e[n] - cum_sum_e[i]
    count_list.append(count)
print(min(count_list))
### BUGGY CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(int(input()))


def solve(ind, choice):
    # ending
    if ind == N:
        num = sum(choice)
        if num % 10 == 0:
            return 0
        else:
            return sum(choice)
    # transition
    return max(solve(ind=ind + 1, choice=choice + [S[ind]]), solve(ind=ind + 1, choice=choice))

print(solve(ind=0, choice=[]))

### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(int(input()))

memo = {}


def solve(ind, points):
    # ending
    if ind == N:
        if points % 10 == 0:
            return 0
        else:
            return points

    if memo.get((ind, points)) is not None:
        return memo[(ind, points)]

    # transition
    ret = max(solve(ind=ind + 1, points=points + S[ind]), solve(ind=ind + 1, points=points))
    memo[(ind, points)] = ret

    return ret

print(solve(ind=0, points=0))
### BUGGY CODE ###

from bisect import *
A,B,Q=map(int,input().split())
S=[int(input()) for i in range(A)]
T=[int(input()) for i in range(B)]
value1=2*(10**10)
for zzz in range(Q):
    x=int(input())
    value=value1
    s1=bisect_left(S,x)
    for s in [s1-1,s1]:
        if -1< s < A:
            t1=bisect_left(T,S[s])
            for t in [t1-1,t1]:
                a=0
                if -1< t < B:
                    if x>S[s]:
                        a+=x-S[s]
                    else:
                        a+=S[s]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a
    t1=bisect_left(T,x)
    for t in [t1-1,t1]:
        if -1< t < B:
            s1=bisect_left(S,T[t])
            for s in [s1-1,s1]:
                a=0
                if -1< s < A:
                    if x>T[t]:
                        a+=x-T[t]
                    else:
                        a+=T[t]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a

    print(value)


### FIXED CODE ###

from bisect import *
A,B,Q=map(int,input().split())
S=[int(input()) for i in range(A)]
T=[int(input()) for i in range(B)]
X=[int(input()) for i in range(Q)]
value1=2*(10**10)
for x in X:
    value=value1
    s1=bisect_left(S,x)
    for s in [s1-1,s1]:
        if -1< s < A:
            t1=bisect_left(T,S[s])
            for t in [t1-1,t1]:
                a=0
                if -1< t < B:
                    if x>S[s]:
                        a+=x-S[s]
                    else:
                        a+=S[s]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a
    t1=bisect_left(T,x)
    for t in [t1-1,t1]:
        if -1< t < B:
            s1=bisect_left(S,T[t])
            for s in [s1-1,s1]:
                a=0
                if -1< s < A:
                    if x>T[t]:
                        a+=x-T[t]
                    else:
                        a+=T[t]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a

    print(value)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N,K=map(int,input().split())
r,s,p=map(int,input().split())
t=[i for i in input()]
tmp=0
for i in range(K):
    if t[i]=='s':
        tmp+=r
    elif t[i]=='p':
        tmp+=s
    else:
        tmp+=p   
    #print(tmp)
    #print('制約なしで勝ち')
flg=0
for i in range(K,N):
    if t[i]!=t[i-K]:
        if t[i]=='s':
            tmp+=r
            #print('グーで勝ち')
        elif t[i]=='p':
            tmp+=s
            #print('チョキで勝ち↓')
        else:
            tmp+=p
            #print('パーで勝ち')
    else:
        t[i]='w'*i
        #print('かぶった（1回目）')
        
            
    #print(tmp)
#print('ans='+str(tmp))
print(tmp)

### FIXED CODE ###

# coding: utf-8
# Your code here!
N,K=map(int,input().split())
r,s,p=map(int,input().split())
t=[i for i in input()]
tmp=0
for i in range(K):
    if t[i]=='s':
        tmp+=r
    elif t[i]=='p':
        tmp+=s
    else:
        tmp+=p   
    #print(tmp)
    #print('制約なしで勝ち')
flg=0
for i in range(K,N):
    if t[i]!=t[i-K]:
        if t[i]=='s':
            tmp+=r
            #print('グーで勝ち')
        elif t[i]=='p':
            tmp+=s
            #print('チョキで勝ち↓')
        else:
            tmp+=p
            #print('パーで勝ち')
    else:
        t[i]='w'
        #print('かぶった（1回目）')
        
            
    #print(tmp)
#print('ans='+str(tmp))
print(tmp)
### BUGGY CODE ###

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

b=[]

for i in range(n-k+1):
    b.append(sum(a[i:i+k]))
    
print((k+max(b))/2)

### FIXED CODE ###

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

ans = sum(a[:k])
b = ans

for i in range(n-k):
    b = b - a[i] + a[i+k]
    if ans < b:
        ans = b       
    
print((k+ans)/2)
### BUGGY CODE ###

n = int(input())
s = input()
a = [s[i+1:].count('E') + s[:i].count('W') for i in range(n)]
print(min(a))

### FIXED CODE ###

n = int(input())
s = input()
left = 0
right = s[1:].count('E')
cnt = [left + right]

for i in range(1, n):
    if s[i-1] == 'W':
        left += 1
    if s[i] == 'E':
        right -= 1
    cnt.append(left + right)

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

MOD = 10**9+7

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

dp=[[1]*(M+1) for i in range(N+1)]
S_index=[[] for i in range(10**5+1)]

for i in range(N):
  S_index[S[i]].append(i)
  for j in range(M):
    dp[i][j]=dp[i][j-1]
    for k in S_index[T[j]]:
      dp[i][j]=(dp[i][j]+dp[k-1][j-1])%MOD
      
print(dp[N-1][M-1])

### FIXED CODE ###

MOD = 10**9+7

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

dp=[[1]*(M+1) for i in range(N+1)]
S_index=[[] for i in range(10**5+1)]

for i in range(N):
  S_index[S[i]].append(i)
  if len(S_index[S[i]])>=2:
    ikkomae=S_index[S[i]][-2]
    for j in range(M+1):
    	dp[i-1][j]=(dp[i-1][j]+dp[ikkomae-1][j])%MOD
  for j in range(M):
    dp[i][j]=dp[i][j-1]
    if len(S_index[T[j]])>=1:
    	dp[i][j]=(dp[i][j]+dp[S_index[T[j]][-1]-1][j-1])%MOD
      
print(dp[N-1][M-1])
### BUGGY CODE ###

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

ans = [0]*N
for i in range(N):
    if i < 2:
        ans[i] = sumA - 2 * sum(A[i+1::2])
    else:
        ans[i] = sumA - 2 * sum(A[i-2::-2]) - 2 * sum(A[i+1::2])

Ans = str(ans)[1:-1].replace(", ", " ")
print(Ans)

### FIXED CODE ###

from itertools import accumulate

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

cumevA = list(accumulate(A[::2]))
cumodA = list(accumulate(A[1::2]))

ans = [None] * N
for i in range(N):
    if i == 0:
        ans[i] = str(sumA - 2 * cumodA[-1])
    elif i == 1:
        ans[i] = str(sumA - 2 * (cumevA[-1] - cumevA[0]))
    elif i == N-1:
        ans[i] = str(sumA - 2 * (cumevA[-2]))
    else:
        if i % 2 == 0:
            ans[i] = str(sumA - 2 * (cumodA[-1] - cumodA[i // 2 - 1] + cumevA[i // 2 - 1]))
        else:
            ans[i] = str(sumA - 2 * (cumevA[-1] - cumevA[(i - 1) // 2] + cumodA[(i - 3) // 2]))

print(" ".join(ans))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
l=1
for i in range(n):
    l*=a[i]
if l>10**18:
    print(-1)
else:
    print(l)

### FIXED CODE ###

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

for i in range(n):
    l*=a[i]
    if l>10**18:
        break
if min(a)==0:
    print(0)
elif l>10**18:
    print(-1)
else:
    print(l)
### BUGGY CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    to = defaultdict(list)
    for _ in range(m):
        s, t = map(int, input().split())
        s, t = s - 1, t - 1
        to[s].append(t)
    ev = [0] * n
    for u in range(n - 2, -1, -1):
        s = 0
        for ku in to[u]:
            s += ev[ku]
        ev[u] = s / len(to[u]) + 1
    ans = ev[0]
    for nu in range(n - 1):
        if len(to[nu]) == 1: continue
        mx = 0
        mv = 0
        for nv in to[nu]:
            if ev[nv] > mx:
                mx = ev[nv]
                mv = nv
        for u in range(nu, -1, -1):
            s = 0
            for ku in to[u]:
                if (u, ku) == (nu, mv): continue
                s += ev[ku]
            od = len(to[u])
            if u == nu: od -= 1
            ev[u] = s / od + 1
        ans = min(ans, ev[0])
    print(ans)

main()


### FIXED CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    to = defaultdict(list)
    for _ in range(m):
        s, t = map(int, input().split())
        s, t = s - 1, t - 1
        to[s].append(t)
    ev = [0] * n
    for u in range(n - 2, -1, -1):
        s = 0
        for ku in to[u]:
            s += ev[ku]
        ev[u] = s / len(to[u]) + 1
    ans = ev[0]
    for nu in range(n - 1):
        if len(to[nu]) == 1: continue
        mx = 0
        mv = 0
        for nv in to[nu]:
            if ev[nv] > mx:
                mx = ev[nv]
                mv = nv
        for u in range(nu, -1, -1):
            s = 0
            for ku in to[u]:
                if (u, ku) == (nu, mv): continue
                s += ev[ku]
            od = len(to[u])
            if u == nu: od -= 1
            ev[u] = s / od + 1
        ans = min(ans, ev[0])
    print(ans)

main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def warshall_floyd(N: int, graph: list) -> list:
    """ ワーシャルフロイド(頂点数, 隣接行列(0-indexed)) """
    from copy import deepcopy

    res = deepcopy(graph)
    for i in range(N):
        # 始点 = 終点、は予め距離0にしておく
        res[i][i] = 0
    # 全頂点の最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                res[i][j] = min(res[i][j], res[i][k] + res[k][j])
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for i in range(N):
        if res[i][i] < 0:
            return []
    return res

N, M, R = MAP()
A = [a-1 for a in LIST()]
G = list2d(N, N, INF)
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    G[a][b] = c
    G[b][a] = c

# 全体グラフの最短距離(ここから必要な頂点間だけ使う)
wf = warshall_floyd(N, G)

ans = INF
for r in range(R):
    # TSP(巡回セールスマン)
    dp = list2d(1<<R, R, INF)
    dp[1<<r][r] = 0
    for bit in range(1, (1<<R)-1):
        for i in range(R):
            if not (bit >> i & 1):
                continue
            for j in range(R):
                if bit >> j & 1:
                    continue
                a, b = A[i], A[j]
                dp[bit|1<<j][j] = min(dp[bit|1<<j][j], dp[bit][i] + wf[a][b])
    ans = min(ans, min(dp[-1]))
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
G = [[float('inf')] * (N) for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    # 経路情報は隣接行列に保持する(無向グラフなので両方向)
    G[a-1][b-1] = c
    G[b-1][a-1] = c

# ワーシャルフロイドで全頂点の最短距離
for k in range(N):
    for i in range(N):
        for j in range(N):
            # 始点 = 終点、は例外的に距離0にしておく
            if i == j:
                G[i][j] = 0
            else:
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])

ans = float('inf')
# 町の順番は順列全部試す(最大8なら大丈夫)
for p in permutations(r):
    sm = 0
    # 最短経路を足し合わせていく
    for i in range(1, len(p)):
        sm += G[p[i-1]-1][p[i]-1]
    ans = min(sm, ans)
print(ans)
### BUGGY CODE ###

a,b,c,d = map(int,input().split())
b = b + 1
count = 0
for i in range(a,b):
  if i % c != 0 and i % d != 0:
    count+=1
print(count)

### FIXED CODE ###

#gcd関数(最大公約数を求める)
from fractions import gcd
a,b,c,d = map(int,input().split())
 
#c,dにおける最小公倍数を求める
z = c*d // gcd(c,d)
#a - 1以下の個数を求める
i = a - 1

#xはb以下で割り切れない個数を求める
x = b - (b // c + b // d - b // z)
#yはa - 1以下で割り切れない個数を求める
y = i - (i // c + i // d - i // z)
#b以下で割り切れない個数からa- 1以下で割り切れない個数引いた個数
print(x - y)
### BUGGY CODE ###

import sys
import math
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))
maps2 = list(maps2)

for i in range(1, H + 1):
    for l in range(1, W + 1):
        maps = copy.deepcopy(maps2)
        if maps2[i][l] != "#":
            pos = [[i, l, 0]]
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth
                maps[y][x] = "$"

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
print(MAX)


### FIXED CODE ###

import sys
import math
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        if maps2[i][l] != "#":
            maps = copy.deepcopy(maps2)
            pos = [[i, l, 0]]
            maps[i][l] = "a"
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                    maps[y + 1][x] = "a"
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                    maps[y][x + 1] = "a"
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                    maps[y - 1][x] = "a"
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
                    maps[y][x - 1] = "a"
print(MAX)
### BUGGY CODE ###

def counter(x):
        if x == 0:
                return 0
        return counter(int(bin(x >> 1), 2)) + int(bin(x & 1), 2)

N = int(input())
A = []
x = [0] * N 
for i in range(N):
        A.append(int(input()))
        x[i] = [list(map(int, input().split())) for j in range(A[i])]

ans = 0 
for bits in range(1, int(bin(1 << N), 2)):
        flag = 1 
        for i in range(N):
                if not int(bin(bits & int(bin(1 << i), 2)), 2): 
                        continue
                for j in range(A[i]):
                        if int(bin(int(bin(bits >> (x[i][j][0] - 1)), 2) & 1), 2) ^ x[i][j][1]:
                                flag = 0 
        if flag:
                ans = max(ans, counter(bits))
print(ans)

### FIXED CODE ###

def counter(x):
        if x == 0:
                return 0
        return counter(x >> 1) + int(bin(x & 1), 2)

N = int(input())
A = []
x = [0] * N 
for i in range(N):
        A.append(int(input()))
        x[i] = [list(map(int, input().split())) for j in range(A[i])]

ans = 0 
for bits in range(1, 1 << N): 
        flag = 1 
        for i in range(N):
                if not int(bin(bits & (1 << i)), 2): 
                        continue
                for j in range(A[i]):
                        if int(bin((bits >> (x[i][j][0] - 1) & 1) ^ x[i][j][1]), 2): 
                                flag = 0 
        if flag:
                ans = max(ans, counter(bits))
print(ans)
### BUGGY CODE ###

from collections import deque

s = deque(list(input()))
n = int(input())
q = [list(input().split()) for _ in range(n)]
for tfc in q:
    if tfc[0] == "1":
        s.reverse()
    else:
        if tfc[1] == "1":
            s.appendleft(tfc[2])
        else:
            s.append(tfc[2])

print("".join(s))


### FIXED CODE ###

from collections import deque

s = deque(list(input()))
n = int(input())
q = [list(input().split()) for _ in range(n)]
rev = False

for tfc in q:
    if tfc[0] == "1" and rev is False:
        rev = True
    elif tfc[0] == "1" and rev is True:
        rev = False
    elif rev is False:
        if tfc[1] == "1":
            s.appendleft(tfc[2])
        else:
            s.append(tfc[2])
    elif rev is True:
        if tfc[1] == "1":
            s.append(tfc[2])
        else:
            s.appendleft(tfc[2])

if rev:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

from bisect import bisect_right as br
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort()
A=[a for a,b in AB]
B=[b for a,b in AB]
works=[]
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  #worksにlatest日以内に報酬を貰える仕事を追加する
  if not A or A[0]>latest:
    pass
  else:
    for _ in range(br(A,latest)):
      A=A[1:]
      index=br(works,B[0])
      works=works[:index]+[B[0]]+works[index:]
      B=B[1:]
  if not works:
    continue
  ans+=works.pop(-1)

print(ans)


### FIXED CODE ###

import heapq
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort(reverse=True)
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  while AB and AB[-1][0]<=latest:
    a,b=AB.pop()
    heapq.heappush(works,-b)
  if not works:
    continue
  ans-=heapq.heappop(works)

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

n = [int(input()) for i in range(1)][0]
li = list(map(int,input().split()))
a = 1
for num in li:
	a *= num
if a > 10**18:
  print(-1)
else:
  print(a)

### FIXED CODE ###

n = [int(input()) for i in range(1)][0]
li = list(map(int,input().split()))
a = 1
while True:
    if 0 in li:
        print(0)
        break
    for num in li:
        a = a * num
        if a <= 10**18:
          continue
        if a > 10**18:
          break
    if a <= 10**18:
        print(a)
        break
    if a > 10**18:
        print(-1)
        break
### BUGGY CODE ###

from collections import defaultdict
N, W = [int(i) for i in input().split()]
Things = [[int(i) for i in input().split()] for j in range(N)]

dp = defaultdict(int)
dp[0] = 0
for w, v in Things:
    for nw, nv in list(dp.items()):
        if nw + w <= W:
            dp[nw + w] = max(dp[nw + w], nv + v)
print(max(dp.values()))

### FIXED CODE ###

from collections import defaultdict
N, W = [int(i) for i in input().split()]
Things = [[int(i) for i in input().split()] for j in range(N)]

dp = defaultdict(lambda: float('inf'))
dp[0] = 0
for w, v in Things:
    for nv, nw in list(dp.items()):
        if nw + w <= W:
            dp[nv + v] = min(dp[nv + v], nw + w)
ans = 0
for v, w in dp.items():
    if w <= W and v >= ans:
        ans = v
print(ans)