Harryxun/stf_run huggingface dataset:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

K = INT()
A = LIST()

def f(N):
	left = N
	for a in A:
		left = left//a*a
	return left

l_N_max = 0
r_N_max = 10**14
while l_N_max+1 < r_N_max:
	m = (l_N_max+r_N_max)//2
	if f(m) <= 2:
		l_N_max = m
	else:
		r_N_max = m

N_max = l_N_max

l_N_min = 0
r_N_min = 10**14
while l_N_min+1 < r_N_min:
	m = (l_N_min+r_N_min)//2
	if f(m) < 2:
		l_N_min = m
	else:
		r_N_min = m
N_min = r_N_min

if N_min > N_max:
	print(-1)
else:
	print(N_min, N_max)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

N, A, B = MAP()

print("Alice" if (abs(A-B)-1)%2 else "Borys")
def main():
    nvertices, nedges = map(int, input().split())
    Adj = [[] for i in range(nvertices)]
    Adjrev = [[] for i in range(nvertices)]
    for i in range(nedges):
        s, t = map(int, input().split())
        Adj[s].append(t)
        Adjrev[t].append(s)

    ordering = []
    visited = [False] * nvertices
    for u in range(nvertices):
        if not visited[u]:
            dfs1(u, Adj, visited, ordering)

    ordering.reverse()
    component_ids = [-1] * nvertices
    id = 0
    visited = [False] * nvertices
    for u in ordering:
        if visited[u]:
            continue
        dfs2(u, Adjrev, id, visited, component_ids)
        id += 1

    Q = int(input())
    for i in range(Q):
        s, t = map(int, input().split())
        if component_ids[s] == component_ids[t]:
            print(1)
        else:
            print(0)


def dfs1(u, Adj, visited, ordering):
    visited[u] = True
    for v in Adj[u]:
        if visited[v]:
            continue
        dfs1(v, Adj, visited, ordering)
    ordering.append(u)

def dfs2(u, Adj, id, visited, component_ids):
    visited[u] = True
    component_ids[u] = id
    for v in Adj[u]:
        if not visited[v]:
            dfs2(v, Adj, id, visited, component_ids)


main()

### FIXED CODE ###

import sys

def main():
    sys.setrecursionlimit(int(1e5))
    nvertices, nedges = map(int, input().split())
    Adj = [[] for i in range(nvertices)]
    AdjRev = [[] for i in range(nvertices)]
    for i in range(nedges):
        u, v = map(int, input().split())
        Adj[u].append(v)
        AdjRev[v].append(u)

    lst = []
    visited = [False] * nvertices
    for u in range(nvertices):
        if not visited[u]:
            dfs_first(u, Adj, visited, lst)

    lst.reverse()
    ids = [-1] * nvertices
    visited = [False] * nvertices
    id = 0
    for u in lst:
        if not visited[u]:
            dfs_second(u, AdjRev, visited, id, ids)
            id += 1

    Q = int(input())
    for i in range(Q):
        u, v = map(int, input().split())
        print(1 if ids[u] == ids[v] else 0)


def dfs_first(u, Adj, visited, lst):
    visited[u] = True
    for v in Adj[u]:
        if not visited[v]:
            dfs_first(v, Adj, visited, lst)
    lst.append(u)


def dfs_second(u, Adj, visited, id, ids):
    ids[u] = id
    visited[u] = True
    for v in Adj[u]:
        if not visited[v]:
            dfs_second(v, Adj, visited, id, ids)

main()
#!/usr/bin/env python
# -*- coding: utf-8 -*-

X = raw_input()
print X/3

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

X = input()
print X//3
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

if __name__ == '__main__':
    a = [str(i) for i in input().split()]

    if a[0] >8 or a[1]>8:
        print("Yay!")
    else:
        print(":(")

### FIXED CODE ###

import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

if __name__ == '__main__':
    a = [int(i) for i in input().split()]

    if a[0] >8 or a[1]>8:
        print(":(")
    else:
        print("Yay!")
4
hoge
english
hoge
enigma


### FIXED CODE ###

N = int(input())
W = input()
L = []
L.append(W)
last = W[-1]
ans = 'Yes'
for _ in range(N-1):
    w = input()
    if w in L:
        ans = 'No'
    if last == w[0]:
        last = w[-1]
        L.append(w)
    else:
        ans = 'No'
print(ans)
N=int(input())
s=input()
R=s.count("R")
G=s.count("G")
B=s.count("B")
ans=R*G*B

#全探索する
for i in range(N-2):
  a=s[i]
  for j in range(i+1,N-1):
    if a==s[j]:
      continue
    b=s[j]
    k=2*j-i
    if "R" not in a+b:
      try:
        if s[k]=="R":
          ans-=1
      except:
        pass
      
    if "G" not in a+b:
      try:
        if s[k]=="G":
          ans-=1
      except:
        pass
      
    if "B" not in a+b:
      try:
        if s[k]=="B":
          ans-=1
      except:
        pass

print(ans)


### FIXED CODE ###

print("Yes" if input().count("7")!=0 else "No")
L R d =map(int, input().split())
ans = 0
for i in range(L, R + 1):
  if i % d == 0:
    ans += 1
print(ans)

### FIXED CODE ###

L, R, d =map(int, input().split())
ans = 0
for i in range(L, R + 1):
  if i % d == 0:
    ans += 1
print(ans)
n = int(raw_input())
a = []
for i in range(n):
    a.append(int(raw_input()))

b = [ 0 if i == max(a) else i for i in a ]
if max(b) == 0:
    b = [ max(a) if i == max(a) else i for i in a ]

print([ max(b) if i == max(a) else max(a) for i in a ])

### FIXED CODE ###

r = int(raw_input())
print(3*r*r)
n=list(map(input().split()))
print("YES" if n==["5","7","5"] or n==["7","5","5"] or n==["5","5","7"] else "NO")

### FIXED CODE ###

l=input().split()
print(["NO","YES"][l.count("7")==1 and l.count("5")==2])
N = int(input())
aa = map(int, input().split())

f = False
for a in aa:
  if a % 2 == 0:
    if (a % 3 != 0) and (a % 5 != 0):
      print('DENIED')
      f = True
      break
if not f:
  print('APPROVED')

### FIXED CODE ###

abc = map(int, input().split())
 
abc_set = set(abc)

if len(abc_set) == 2:
  print('Yes')
else:
  print('No')
a = int(input())
b = int(input())

s = int((a + b) * 2)
m = int(a * b)
print(m, s)

### FIXED CODE ###

a, b = list(map(int, input().split()))
c = (a + b) * 2
d = a * b
print(str(d) + " " + str(c))
n = int(input())
heights = list(map(int, input().split()))

def nextgen(comb):
    lis = comb[0]
    j = comb[1]
    for i in range(len(lis)-1):
        if (i != len(lis) and (lis[i] == 0 and lis[i+1] != 0)) or (i == 0 and lis[i] != 0):
            j += 1
        if lis[i] != 0:
            lis[i] -= 1
    if lis[len(lis)-1] != 0:
        lis[len(lis)-1] -= 1
    return [lis, j]

comb = [heights, 0]
while (comb[0].count(0) != len(comb[0])):
    comb = test(comb)

print(comb[1])

### FIXED CODE ###

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

def nextgen(comb):
    lis = comb[0]
    j = comb[1]
    if len(lis) == 1 and lis[0] != 0:
        j += 1  
    for i in range(len(lis)-1):
        if (i != len(lis) and (lis[i] == 0 and lis[i+1] != 0)) or (i == 0 and lis[i] != 0):
            j += 1
        if lis[i] != 0:
            lis[i] -= 1
    if lis[len(lis)-1] != 0:
        lis[len(lis)-1] -= 1
    return [lis, j]

comb = [heights, 0]
while (comb[0].count(0) != len(comb[0])):
    comb = nextgen(comb)

print(comb[1])
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    n = int(input())
    a = list(map(int,readline().split()))

    def factorization(n):
        factors = []

        if n < 2:
            return n

        while n % 2 == 0:
            factors.append(2)
            n //= 2

        for i in range(3, int(n ** 0.5) + 5, 2):
            while n % i == 0:
                factors.append(i)
                n //= i
        if n != 1:
            factors.append(n)

        return Counter(factors)

    a_fac = [0] * n

    for i, num in enumerate(a):
        a_fac[i] = factorization(num)

    lcm = Counter([1])

    for i, fac in enumerate(a_fac):
        add = +(fac - lcm)
        lcm += add

    b = [0] * n

    for i, fac in enumerate(a_fac):
        b_fac = lcm - fac
        temp = 1
        for key, value in b_fac.items():
            temp *= pow(key, value, MOD)
            temp %= MOD
        b[i] = temp

    ans = 0
    for elem in b:
        ans += elem
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    n = int(input())
    a = list(map(int, readline().split()))

    def factorization(n):
        factors = []

        while n % 2 == 0:
            factors.append(2)
            n //= 2

        for i in range(3, int(n ** 0.5) + 5, 2):
            while n % i == 0:
                factors.append(i)
                n //= i
        if n != 1:
            factors.append(n)

        return Counter(factors)

    a_fac = [0] * n

    for i, num in enumerate(a):
        a_fac[i] = factorization(num)

    lcm = {1: 1}

    for fac in a_fac:
        for key, value in fac.items():
            lcm[key] = max(lcm.get(key, 0), value)

    ans = 0

    lcmmod = 1

    for key, value in lcm.items():
        lcmmod *= pow(key, value, MOD)
        lcmmod %= MOD

    for ele in a:
        ainv = pow(ele, MOD - 2, MOD)
        ans += ((lcmmod*ainv) % MOD)
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()
S = input()
w = int(input())
count=0
str = ""
while(count <= len(S)):
    str += S[count]
    count += w
print(str)

### FIXED CODE ###

s = raw_input()
w = int(raw_input())

ss = ''

for i in xrange(0, len(s), +w): ss += s[i]

print ss
a = input()
b = len(list(a))
c = int(a)
d = ''

if b % 2 == 0:
    d = '9' * (b // 2)
    print('0'.join(d))

else:
    if b > 1:
        d = '9' * (b // 2)
    '0'.join(d)
    d = int(d)
    print(d + int(a[1:]) + 1)

### FIXED CODE ###

a = input()
b = len(list(a))
c = int(a)
d = ''

if b % 2 == 0:
    d = '9' * (b // 2)
    print('0'.join(d))

else:
    if b == 1:
        print(a)
    else:
        d = '9' * (b // 2)
        d = '0'.join(d)
        d = int(d + '0')
        print(c - d)
N = int(input())

print((N*(N-1))//2)

### FIXED CODE ###

ss = input()
tt = input()

c = 0
for s, t in zip(ss, tt):
    if s == t and (s == 'R' or s == 'C' or s == 'S'):
       c += 1

print(c)
S = input()
K = int(input())
length = len(S)
alpha, n = 'abcdefghijklmnopqrstuvwxyz', 26
i = 0
ans = ''
while i < length:
    diff = (n - (ord(S[i]) - ord('a'))) % 26
    
    if 0 <= diff <= K:
        ans += 'a'
        K -= diff
    else:
        ans += S[i]
        
    i += 1
    if K == 0:
        ans += S[i:]
else:
    ans = ans[:-1] + chr(ord(ans[-1]) + K % 26)
print(ans)

### FIXED CODE ###

S = input()
K = int(input())
length = len(S)
alpha, n = 'abcdefghijklmnopqrstuvwxyz', 26
i = 0
ans = ''
while i < length:
    diff = (n - (ord(S[i]) - ord('a'))) % 26
    
    if 0 <= diff <= K:
        ans += 'a'
        K -= diff
    else:
        ans += S[i]
    i += 1
if K: ans = ans[:-1] + chr(ord('a') + (ord(ans[-1]) - ord('a') + K) % 26)
print(ans)
ans=0
n=input()
s=input()


for i in s:
    if i=="A":
        flag="a"
    elif i=="B" and flag=="a":
        flag="b"
    elif i=="C" and flag=="b":
        flag="0"
        ans+=1
    else:
        flag="0"
print(ans)

### FIXED CODE ###

ans=0
n=input()
s=input()
flag="0"

for i in s:
    if i=="A":
        flag="a"
    elif i=="B" and flag=="a":
        flag="b"
    elif i=="C" and flag=="b":
        flag="0"
        ans+=1
    else:
        flag="0"
        
print(ans)
S = int(input())


def prime_factorize(n):
    a = 1
    while n % 2 == 0:
        n //= 2
        a *= 2

    if n <= 10 ** 9:
        return n
    f = 3
    while f * f <= n:
        if S // a <= 10 ** 9:
            return a
        if n % f == 0:
            n //= f
            a *= f
        else:
            f += 2


if S <= 10 ** 9:
    print(0, 0, 1, 0, 0, S)
else:
    x = prime_factorize(S)
    y = S // x
    print(0, 0, x, 0, 0, y)

### FIXED CODE ###

S = int(input())

if S != 10 ** 18:
    q = S // 10 ** 9 + 1
    r = 10 ** 9 * q - S
else:
    q = S // 10 ** 9
    r = 10 ** 9 * q - S

print(0, 0, q, r, 1, 10 ** 9)
A, B, K = map(int, input().split())
nums = []
num_range = list(range(A, B + 1))
for i in range(K if (B + 1 - A) > K else (B + 1 - A)):
    nums.append(num_range[i])
    nums.append(num_range[- (i + 1)])
for num in sorted(list(set(nums))):
    print(num)


### FIXED CODE ###

A, B, K = map(int, input().split())
num_range = range(A, B + 1)
for i in sorted(set(num_range[:K]) | set(num_range[-K:])):
    print(i)
n=int(input())
h=list(map(int,input().split()))
c=0
t=[]
for i in range(n-1):
  if h[i]>=h[i+1]:
    c+=1
  else:
    t.append(c)
    c=0
  t.append(c)
print(max(t))
    

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
c=0
t=0

for i in range(n-1):
  if h[i]>=h[i+1]:
    c+=1
  else:
    t=max(t,c)
    c=0
  t=max(t,c)
print(t)
N = int(input())
reds = sorted([list(map(int,input().split())) for i in range(n)])
blues = sorted([list(map(int,input().split())) for i in range(n)])

reds.sort(reverse = True)
res = 0

for c,d in blues:
  for a,b in reds:
    if a<c and b<d:
      reds.remove([a,b])
      res+=1
      break
      
print(res)


### FIXED CODE ###

A,B,C = list(map(int,input().split()))
if (A+B)>=C:
    print('Yes')
else:
    print('No')
h, w = [int(n) for n in input().split()]
i = min(h, w)
j = max(h, w)
area = i * j
if i % 3 == 0 or j % 3 == 0:
    print(0)
else:
    p = j // 3 + 1
    pp = i // 3 + 1
    q = j // 3 - 1
    qq = i // 3 - 1
    a1 = i * p
    aa1 = j * p
    a2 = i * q
    aa2 = j * q
    b1 = i // 2 * (j - p)
    bb1 = j // 2 * (i - p)
    b2 = i // 2 * (j - q)
    bb2 = j // 2 * (i - q)
    c1 = (j - p) // 2 * i
    cc1 = (i - p) // 2 * j
    c2 = (j - q) // 2 * i
    cc2 = (i - q) // 2 * j

    print(min(
        abs(a1 - b1), abs(aa1 - bb1), abs(aa2 - bb2), abs(a2 - b2)
        abs(a1 - c1), abs(aa1 - cc1), abs(aa2 - cc2), abs(a2 - c2)
    ))

### FIXED CODE ###

h, w = [int(n) for n in input().split()]
i = min(h, w)
j = max(h, w)
area = i * j
if i % 3 == 0 or j % 3 == 0:
    print(0)
else:
    lst = []
    for r, s in [(i, j), (j, i)]:
        
        p = s // 3 + 1
        q = s // 3 
        a1 = r * p
        a2 = r * q
        b1 = r // 2 * (s - p)
        bb1 = (r // 2 - 1) * (s - p)
        b2 = r // 2 * (s - q)
        bb2 = (r // 2 - 1) * (s - q)
        c1 = (s - p) // 2 * r
        cc1 = ((s - p) // 2- 1) * r
        c2 = (s - q) // 2 * r
        cc2 = ((s - q) // 2 - 1) * r
        tup = [(a1, b1), (a2, b2), (a1, c1), (a2, c2),
               (a1, bb1), (a2, bb2), (a1, cc1), (a2, cc2)]
        lst.extend([abs(max(a, b, area - a - b) - min(a, b, area - a - b))
                    for a, b in tup])
    print(min(lst))
N= int(input())
A = list(map(int,input().split()))
dict_L = {}
#dict_R = {}
for i in range(-max(A),N+max(A)):
    dict_L[i] = 0
    #dict_R[i] = 0
for i in range(N):
    dict_L[i+1+A[i]] += 1
    #dict_R[i-A[i]] += 1
cnt = 0
for j in range(N):
    R = j+1-A[j]
    cnt += dict_L[R]
print(cnt)

### FIXED CODE ###

N= int(input())
A = list(map(int,input().split()))
dict_L = {}
for i in range(N):
    if(i+1+A[i] in dict_L.keys()):
        dict_L[i+1+A[i]] += 1
    else:
        dict_L[i+1+A[i]] = 1
cnt = 0
for j in range(N):
    R = j+1-A[j]
    if(R in dict_L.keys()):
        cnt += dict_L[R]
print(cnt)
s = [input() for i in range(2)]
S = s[0]
T = s[1]
print(S)
print(T)


def count_diff2(s, t):
    cnt = 0
    for c1,c2 in zip(s, t):
        if c1 != c2:
            cnt += 1
    return cnt

print(count_diff2(S, T))

### FIXED CODE ###

# -*- coding: utf-8 -*-
val_1 = int(input())
val_2 = val_1 * val_1
val_3 = val_1 * val_1 * val_1

answer = val_1 + val_2 + val_3
print(answer)
n,a,b = map(int, input().split())
min_num = 0
max_num = 0

if a == b and a == n:
    min_num = n
    max_num = n
elif a == n or b == n
    min_num = min(a,b)
    max_num = min(a,b)
elif a == 0 or b == 0:
    pass
elif n >= a + b:
    max_num = min(a,b)
elif n < a + b:
    min_num = abs(int(n/2)-max(a,b))
    max_num = min(a,b)

print(max_num, min_num)


### FIXED CODE ###

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

if a == n or b == n:
    min_num = min(a,b)
    max_num = min(a,b)
elif a == b and a == n:
    min_num = n
    max_num = n
elif a == 0 or b == 0:
    pass
elif n >= a + b:
    max_num = min(a,b)
elif n < a + b:
    min_num = abs(n-a-b)
    max_num = min(a,b)

print(max_num, min_num)
n, m = map(int,raw_input().split())
matrix = []
for i in range(n):
    matrix.append(map(int,raw_input().split()))

vector = []
for i in range(m):
    vector.append(int(raw_input()))

for i in range(m):
    for j in range(n):
        print sum([vector[j] * matrix[i][j]])

### FIXED CODE ###

n, m = map(int,raw_input().split())
matrix = []
for i in range(n):
    matrix.append(map(int,raw_input().split()))
 
vector = []
for i in range(m):
    vector.append(int(raw_input()))
 
for row in range(n):
    sum = 0
    for col in range(m):
        sum += vector[col] * matrix[row][col]
    print sum
n, m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
from collections import deque
import bisect
d = deque(A)
for _ in range(m):
    max_ = d.pop()
    tmp = max_ // 2
    index = bisect.bisect_left(d, tmp)
    d.insert(index, tmp)
print(sum(d))

### FIXED CODE ###

n, m = map(int,input().split())
A = list(map(int,input().split()))
A = [x * -1 for x in A]
A.sort()
import heapq
import bisect
heapq.heapify(A)
for _ in range(m):
    min_ = heapq.heappop(A)
    tmp = min_ * -1 // 2 * -1
    index = bisect.bisect_left(A, tmp)
    heapq.heappush(A,tmp)
print(sum(A) * -1)
C = list(map(int, input().split()))
A.append("")
B.append("")
ans=0
for i in range(1,N+1):
	ans+=B[A[i-1]-1]
	if A[i-1]==A[i]-1:
		ans+=C[A[i-2]]
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.append(100)
B.append(100)
C.insert(0,0)
ans=0
for i in range(1,N+1):
	ans+=B[A[i-1]-1]
	if A[i-1]==A[i]-1:
		ans+=C[A[i-1]]
print(ans)
a = int(input())

    X = int(a/1.08 + 0.9)

    if int(X*1.08) == a: 
        print(X)
    else:
        print(":(")

### FIXED CODE ###

import math
a = int(input())

X = math.ceil(a/1.08)

if math.floor(X*1.08) == a: 
    print(X)
else:
    print(":(")
n = int(input())
d = {
for i in range(n):
  card = input()
  cards[card] = 1
  
for c in ['S','H','C','D']:
  for n in range(1,14):
    card = c + ' ' + str(n)
    if not key in cards:
      print(card)


### FIXED CODE ###

n = int(input())
cards = {}
for i in range(n):
  card = input()
  cards[card] = 1

for c in ['S', 'H', 'C', 'D']:
  for n in range(1,14):
    key = c + ' ' + str(n)
    if not key in cards:
      print(key)
x=1 ≤ x ≤ 100
a=x*x*x
print(a)


### FIXED CODE ###

print(int(input())**3)
def IN(): return map(int,input().split())
ans = pow(2,31); mod = pow(10,9)+7
h,n=IN()
A=[]; dp=[pow(2,31)]*11111
for i in range(n):
  x,y=IN()
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(10111):
    dp[i+a]=min(dp[i+a],dp[i]+b)
for i in range(h,11111):
  ans=min(ans,dp[i])
print(ans)

### FIXED CODE ###

def IN(): return map(int,input().split())
ans = pow(2,31); mod = pow(10,9)+7
h,n=IN()
A=[]; dp=[pow(2,31)]*111111
for i in range(n):
  x,y=IN()
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(h+1111):
    dp[i+a]=min(dp[i+a],dp[i]+b)
for i in range(h,11111):
  ans=min(ans,dp[i])
print(ans)
n,m = map(int,input().split())
INF = 10**18
d = [[INF]*n for _ in range(n)]
for i in range(n): d[i][i] = 0
a = [0]*m
b = [0]*m
c = [0]*m
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    a[i] = a
    b[i] = b
    c[i] = c
    d[a][b] = c
    d[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k]+d[k][j])

ans = 0
for i in range(m):
    if d[a[i]][b[i]] < c[i]: ans += 1
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
INF = 10**18
d = [[INF]*n for _ in range(n)]
nd = [[INF]*n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
    nd[i][i] = 0
for _ in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
    nd[a][b] = c
    nd[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            nd[i][j] = min(nd[i][j], nd[i][k]+nd[k][j])

cnt = 0
for i in range(n):
    for j in range(n):
        if d[i][j] == INF: continue
        if nd[i][j] < d[i][j]: cnt += 1
print(cnt//2)
import sys
N, M = map(int, input().split())
d = {}
for _ in range(M):
  s, c = input().split()
  if s in d and d[s] != c:
    print("-1")
    sys.exit()
  else:
    d[s] = c
if N == 3:
  if d["1"] == "0":
    print("-1")
    sys.exit()
  else:
    if "1" not in d:
      a = "1"
    else:
      a = d["1"]
    if "2" in d:
      b = d["2"]
    else:
      b = "0"
    if "3" in d:
      c = d["3"]
    else:
      c = "0"
  print(a + b + c)
  sys.exit()
  
if N == 2:
  if d["2"] == "0":
    print("-1")
    sys.exit()
  else:
    if "2" in d:
      b = d["2"]
    else:
      b = "0"
    if "3" in d:
      c = d["3"]
    else:
      c = "0"
  print(b + c)
  sys.exit()
  
if N == 1:
  if d["3"] == "0":
    print("-1")
    sys.exit()
  else:
    if "3" in d:
      c = d["3"]
    else:
      c = "0"
  print(c)

### FIXED CODE ###

import sys
N, M = map(int, input().split())
d = {}
for _ in range(M):
  s, c = input().split()
  if s in d and d[s] != c:
    print("-1")
    sys.exit()
  else:
    d[s] = c
    
if N == 3:
  if "1" in d and d["1"] == "0":
    print("-1")
    sys.exit()
  else:
    if "1" not in d:
      a = "1"
    else:
      a = d["1"]
    if "2" in d:
      b = d["2"]
    else:
      b = "0"
    if "3" in d:
      c = d["3"]
    else:
      c = "0"
  print(a + b + c)
  sys.exit()
  
if N == 2:
  if "1" in d and d["1"] == "0":
    print("-1")
    sys.exit()
  else:
    if "1" in d:
      b = d["1"]
    else:
      b = "1"
    if "2" in d:
      c = d["2"]
    else:
      c = "0"
  print(b + c)
  sys.exit()
  
if N == 1:
  if "1" in d and d["1"] == "0":
    print("0")
    sys.exit()
  else:
    if "1" in d:
      c = d["1"]
    else:
      c = "0"
  print(c)