Harryxun/stf_run huggingface dataset:
N = int(input())
S = input()
a = [0] * N
b = [0] * N
counter = []

if S[0] == '#':
    a[0] = 1
if S[N-1] == '.':
    b[N-1] = 1

for i in range(N-1):
    if S[i+1] == '#':
        a[i+1] = a[i] + 1
    else:
        a[i+1] = a[i]
    if S[N-i-2] =='.':
        b[N-i-2] = b[N-i-1] + 1
    else:
        b[N-i-2] = b[N-i-1]
        
for i in range(N-1):
    counter.append(a[i] + b[i+1])

print(min(counter))


### FIXED CODE ###

N = int(input())
S = input()
a = [0] * N
b = [0] * N
counter = []

if S[0] == '#':
    a[0] = 1
if S[N-1] == '.':
    b[N-1] = 1

for i in range(N-1):
    if S[i+1] == '#':
        a[i+1] = a[i] + 1
    else:
        a[i+1] = a[i]
    if S[N-i-2] =='.':
        b[N-i-2] = b[N-i-1] + 1
    else:
        b[N-i-2] = b[N-i-1]
counter.append(a[N-1])
counter.append(b[0])
for i in range(N-1):
    counter.append(a[i] + b[i+1])

print(min(counter))
a,b=map(int,input().split());s=input();print(""[len(s)<11*s[a]=="-"::2]

### FIXED CODE ###

a,b=map(int,input().split())
s=input()
if s.count("-")<2 and s[a]=="-":
  print("Yes")
else:
  print("No")
n,m=map(int,input().split())
lm=[]
m1=m
if m!=0:
  while m1!=0:
    lm.append(m1%2)
    m1=m1//2
else:
  lm=[0]
ln=[]
n1=n-1
if n!=0:
  while n1!=0:
    ln.append(n1%2)
    n1=n1//2
while len(ln)!=len(lm):
  ln.append(0)
lm1=[0 for i in range(len(lm))]
ln1=[0 for i in range(len(ln))]
if lm[0]!=lm[1]:
  lm1[0]=1
if ln[0]!=ln[1]:
  ln1[0]=1
for i in range(1,len(lm)):
  if lm[i]==1 and lm[0]==0:
    lm1[i]=1
for i in range(1,len(ln)):
  if ln[i]==1 and ln[0]==0:
    ln1[i]=1
lmn=[0 for i in range(len(lm))]
for i in range(len(lm)):
  if lm1[i]==ln1[i]:
    pass
  else:
    lmn[i]=1
s=1
ss=0
for i in lmn:
  ss+=s*i
  s*=2
print(ss)


### FIXED CODE ###

n,m=map(int,input().split())
lm=[]
m1=m
if m!=0:
  while m1!=0:
    lm.append(m1%2)
    m1=m1//2
else:
  lm=[0]
ln=[]
n1=n-1
if n!=0:
  while n1!=0:
    ln.append(n1%2)
    n1=n1//2
while len(ln)!=len(lm):
  ln.append(0)
if n!=0:
  lm1=[0 for i in range(len(lm))]
  ln1=[0 for i in range(len(ln))]
  if lm[0]!=lm[1]:
    lm1[0]=1
  if ln[0]!=ln[1]:
    ln1[0]=1
  for i in range(1,len(lm)):
    if lm[i]==1 and lm[0]==0:
      lm1[i]=1
  for i in range(1,len(ln)):
    if ln[i]==1 and ln[0]==0:
      ln1[i]=1
  lmn=[0 for i in range(len(lm))]
  for i in range(len(lm)):
    if lm1[i]==ln1[i]:
      pass
    else:
      lmn[i]=1
  s=1
  ss=0
  for i in lmn:
    ss+=s*i
    s*=2
  print(ss)
else:
  print(m)
from collections import deque
N, Q = map(int, input().split())
S = input()
l = [0 for i in range(Q)]
r = [0 for i in range(Q)]

for i in range(Q):
    l[i], r[i] = map(int, input().split())

for i in range(Q):
    s = S[l[i]-1:r[i]]
    print(s.count('AC'))

### FIXED CODE ###

b = input()
if b == 'A':
    print('T')
if b == 'T':
    print('A')
if b == 'G':
    print('C')
if b == 'C':
    print('G')
# -*- coding:utf8 -*-

n = int(input())
h = list(map(int, input().split()))
p = h[0]
l = [p]
for i in range(1,n):
    c = h[i]
    if i == 1 and p - 1 == c:
        l[0] == c
    if p < c:
        C -= 1
    l.append(c)
    p = c
ans = 'Yes' if l == sorted(l) else 'No'
print(ans)

### FIXED CODE ###

# -*- coding:utf8 -*-

n = int(input())
h = list(map(int, input().split()))
p = h[0]
l = [p]
for i in range(1,n):
    c = h[i]
    if i == 1 and p - 1 == c:
        l[0] == c
    if p < c:
        c -= 1
    l.append(c)
    p = c
ans = 'Yes' if l == sorted(l) else 'No'
print(ans)
s = list(str(input()))
x,y = map(int,input().split())

i = 0
while i < len(s) and s[i] =="F":
    i += 1
x -= i
s = s[i:]

m = [[],[]]
num = 0

for i in range(len(s)):
    if s[i] == "F":
        m[num][-1] += 1
    else:
        num += 1
        num %= 2
        m[num].append(0)

#print("m",m)

sumx = sum(m[0])
dpx = [False]*(2*sumx+3) #index(sumx+1)が座標0
dpx[sumx+1] = True
#print("dpx",dpx)

for p in m[0]:
    dpx_pre = dpx[:]
    dpx = [False]*(2*sumx+3)
    for i in range(2*sumx+3):
        if i-p >= 0 and (dpx[i-p] == False):
            dpx[i-p] = dpx_pre[i]
            #print("dpx",dpx)
        if i+p < 2*sumx+3 and (dpx[i+p] == False):
            dpx[i+p] = dpx_pre[i]
            #print("dpx",dpx)
    #print("dpx",dpx)

sumy = sum(m[1])
dpy = [False]*(2*sumy+3) #index(sumy+1)が座標0
dpy[sumy+1] = True
#print("dpy",dpy)

for p in m[1]:
    dpy_pre = dpy[:]
    dpy = [False]*(2*sumy+3)
    for i in range(2*sumy+3):
        if i-p >= 0 and (dpy[i-p] == False):
            dpy[i-p] = dpy_pre[i]
        if i+p < 2*sumy+3 and (dpy[i+p] == False):
            dpy[i+p] = dpy_pre[i]
    #print("dpy",dpy)

if dpx[x+(sumx+1)] == True and dpy[y+(sumy+1)] == True:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = list(str(input()))
x,y = map(int,input().split())

i = 0
while i < len(s) and s[i] =="F":
    i += 1
x -= i
s = s[i:]

m = [[],[]]
num = 0

for i in range(len(s)):
    if s[i] == "F":
        m[num][-1] += 1
    else:
        num += 1
        num %= 2
        m[num].append(0)

#print("m",m)

sumx = sum(m[0])

dpx = [False]*(2*sumx+3) #index(sumx+1)が座標0
dpx[sumx+1] = True
#print("dpx",dpx)

for p in m[0]:
    dpx_pre = dpx[:]
    dpx = [False]*(2*sumx+3)
    for i in range(2*sumx+3):
        if i-p >= 0:
            dpx[i-p] = dpx_pre[i] or dpx[i-p]
            #print("dpx",dpx)
        if i+p < 2*sumx+3:
            dpx[i+p] = dpx_pre[i] or dpx[i+p]
            #print("dpx",dpx)
    #print("dpx",dpx)

sumy = sum(m[1])
dpy = [False]*(2*sumy+3) #index(sumy+1)が座標0
dpy[sumy+1] = True
#print("dpy",dpy)

for p in m[1]:
    dpy_pre = dpy[:]
    dpy = [False]*(2*sumy+3)
    for i in range(2*sumy+3):
        if i-p >= 0:
            dpy[i-p] = dpy_pre[i] or dpy[i-p]
        if i+p < 2*sumy+3:
            dpy[i+p] = dpy_pre[i] or dpy[i+p]
    #print("dpy",dpy)

if abs(x) > sumx+1 or abs(y) > sumy+1:
    print("No")
elif dpx[x+(sumx+1)] and dpy[y+(sumy+1)]:
    print("Yes")
else:
    print("No")
a,b=map(int,input().split())
k=(a+b)//2
print(k if ((a>=k and b<=k) or (a<=K and b>=k)) and k%2==0 else "IMPOSSIBLE")

### FIXED CODE ###

a,b=map(int,input().split())
print((a+b)//2 if (a+b)%2==0 else "IMPOSSIBLE")
A, B, C, D = map(int, input.split())
print(max(A*B, C*D))

### FIXED CODE ###

A, B, C, D = map(int, input().split())
print(max(A*B, C*D))
N,M = map(int, input().split())

from collections import defaultdict
E = []

for i in range(M):
  a,b,c = map(int, input().split())
  a,b = a-1, b-1
  E += [(a,b,c)]

def reachable_vertices(neighbor, s):
  V = set()
  V.add(s)
  stack=[s]
  while stack:
    v = stack.pop()
    for u in neighbor[v]:
      if u not in V:
        V.add(u)
        stack.append(u)
  return V

def neighbor_dict(E):
  neighbor = defaultdict(list)
  for a,b,c in E:
    neighbor[a].append(b)
  return neighbor

def rev_neighbor_dict(E):
  neighbor = defaultdict(list)
  for a,b,c in E:
    neighbor[b].append(a)
  return neighbor

def degenerate_graph(V, E):
  d = {v:i for i,v in enumerate(sorted(V))}
  return len(V), [(d[a],d[b],c) for a,b,c in E]

# only vertices that are reachable from 1 or N
N,E = degenerate_graph(reachable_vertices(neighbor_dict(E), 0), E)
N,E = degenerate_graph(reachable_vertices(rev_neighbor_dict(E), N-1), E)
score = [float('-inf')]*N
score[0] = 0


i = 0
updated=True
while updated:
  if i == N:
    print('inf')
    break

  updated = False
  for a,b,w in E:
    if score[b] < score[a] + w:
      score[b] = score[a] + w
      updated = True
  i += 1
else:
  print(score[N-1])

### FIXED CODE ###



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

from collections import defaultdict
neighbor = defaultdict(list)
Rneighbor = defaultdict(list)
edges = []
for i in range(M):
  a,b,c = map(int, input().split())
  a,b = a-1, b-1
  edges += [(a,b,c)]
  neighbor[a].append(b)
  Rneighbor[b].append(a)

# only vertices that are reachable from 1 or N
v1 = set()
v1.add(0)
stack = [0]
while stack:
  v = stack.pop()
  for u in neighbor[v]:
    if u not in v1:
      v1.add(u)
      stack.append(u)

vn = set()
vn.add(N-1)
stack = [N-1]
while stack:
  v = stack.pop()
  for u in Rneighbor[v]:
    if u not in vn:
      vn.add(u)
      stack.append(u)

V = v1 & vn

edges = [(a,b,c) for a,b,c in edges if a in V and b in V]
score = [float('-inf')]*N
score[0] = 0

updated = True
i = 0

positive_cycle = False

while updated:
  if i == len(V):
    positive_cycle = True
    break

  updated = False
  for a,b,w in edges:
    if score[b] < score[a] + w:
      score[b] = score[a] + w
      updated = True
  i += 1

if positive_cycle:
  print('inf')
else:
  print(score[N-1])
from operator import itemgetter
n = int(input())
A = input().split()
for i in range(n):
  A[i] = [int(A[i]),i+1]
A = sorted(A, key=itemgetter(0))
for a in A:
  print(a[1],end=" ")

### FIXED CODE ###

n = int(input())
print( int((n+1)/2)/n )
n = int(input())
v = list(map(int, input().split())) 
a = 0
b = [0]*(10**5+10)
c = [0]*10**5
d = [0]*10**5
e = [0]*10**5
for i in range(n-1):
  if v[i]==v[i+1]:
    a +=1
if(a == n-1):
  print(int(n/2))
else:
  for i in range(0,n,2):
    b[v[i]] = b[v[i]] + 1
  for j in range(1,n+1,2):
    c[v[j]] =c[v[j]] + 1
  d = sorted(b,reverse=True)
  e = sorted(c,reverse=True)
  f = int(n/2)-d[0]
  g = int(n/2)-e[0]
  print(f+g)

### FIXED CODE ###

n = int(input())
v = list(map(int, input().split())) 
a = 0
ab = 0
ac = 0
b = [0]*(10**5+10)
c = [0]*(10**5+10)
d = [0]*(10**5+10)
e = [0]*(10**5+10)
for i in range(n-1):
  if v[i]==v[i+1]:
    a +=1
if(a == n-1):
  print(int(n/2))
else:
  for i in range(0,n,2):
    b[v[i]] = b[v[i]] + 1
  for j in range(1,n+1,2):
    c[v[j]] =c[v[j]] + 1
  d = sorted(b,reverse=True)
  e = sorted(c,reverse=True)
  for s in range(10**5+1):
    if(d[0]==b[s]):
      ab = s
      break
  for t in range(10**5+1):
    if(e[0]==c[t]):
      ac = t
      break
  if(s==t):
    print(min(2*int(n/2)-d[0]-e[1],2*int(n/2)-d[1]-e[0]))
  else: 
    f = int(n/2)-d[0]
    g = int(n/2)-e[0]
    print(f+g)
n,k=map(int,input().split())
a,b=map(int,input().split())
s=[]
s+=[a]*b
for i in range(n-1):
  a,b=map(int,input().split())
  if a>s[-1]:
    continue
  s+=[a]*b
  p=sorted(s)[:k]
print(p[k-1])

### FIXED CODE ###

n,k=map(int,input().split())
d=[0]*(10**5+1)
for i in range(n):
  a,b=map(int,input().split())
  d[a]+=b
for i in range(10**5+1):
  if d[i]>=k:
    print(i)
    break
  else:k-=d[i]
import numpy as np
N,X,Y=map(int, input().split())
ans = [0]*(N-1)
for i in range(1,N):
  for j in range(i+1,N+1):
    root1 = j-i
    root2 = abs(X-i) + 1 + abs(Y-j)
    min_k = min(root1, root2)
    ans[min_k-1] = ans[min_k-1] + 1

for a in ans:
  print(a)

### FIXED CODE ###

import numpy as np
N,X,Y=map(int, input().split())
ans = [0]*(N-1)
for i in range(1,N):
  for j in range(i+1,N+1):
    root1 = j-i
    root2 = abs(X-i) + 1 + abs(Y-j)
    min_k = min(root1, root2)
    ans[min_k-1] = ans[min_k-1] + 1

for a in ans:
  print(a)
import numpy as np
from sys import stdin

def main():
    nm = [int(x) for x in stdin.readline().rstrip().split()]
    gate = np.full([nm[1], nm[0]], False)
    
    for i in range(nm[1]):
        g = [int(x) for x in stdin.readline().rstrip().split()]
        for k in range(g[0]-1, g[1]):
            gate[i,k] = True

    count = 0
    for i in range(len(gate[0])):
        tmp = gate[:, i]
        if tmp.all():
            count += 1
        
    print(count)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
from sys import stdin
#sys.setrecursionlimit(10**6) 

def main():
    a, b = [int(x) for x in stdin.readline().rstrip().split()]
    if 6 <= a and a <= 12:
        v = b//2
    elif a <= 5:
        v = 0
    else:
        v = b
    print(v)

if __name__ == "__main__":
    main()
n = input()
num = []
num = input().split(" ")
 
t = 0 
a=0 
while True: 
  num2=[] 
  for i in num: 
    if not (int(i)%2): 
    	a =1 
        break 
    num2.append(int(i)%2) 
    num = num2 
    t+=1 
    if a==1: 
       print(t) 
       break

### FIXED CODE ###

n = input()
num = []
num = input().split(" ")
 
t = 0 
a=0 
while True: 
  num2=[] 
  for i in num: 
    if not int(i)%2==0:
      a =1
      break
    num2.append(int(i)/2)
  num = num2
  if a==1: 
     print(t) 
     break
  t+=1
n,c=map(int,input().split())
x=[0]
v=[]
for i in range(n):
    a,b=map(int,input().split())
    x.append(a)
    v.append(b)

x1=[x[i+1]-x[i] for i in range(len(x)-1)]
x2=[c-x[-1]]+x1[:0:-1]
h=[0]
for i,j in zip(x2,reversed(v)):
    h.append(h[-1]+j+-i)
t=[0]
for i,j in zip(x1,v):
    t.append(t[-1]+j-i)
hi=h.index(max(h[0:-1]))
ti=t.index(max(t[0:-1]))
tm=max(t[0:-1])
hm=max(h[0:-ti])
h2=[h[i]-c+x[-i] for i in range(1,len(h)-1)]
t2=[t[i]-x[i] for i in range(1,len(t)-1)]


#print(ti,hi)
print(max(max(t), max(h), hm+max(t2[0:-ti]),tm+max(h2[:-hi])))

### FIXED CODE ###

n,c=map(int, input().split())
a=[[0,0]]+[list(map(int, input().split())) for i in range(n)]+[[c,0]]
m=[0]
h=[0]
mb=[0]
hb=[0]
for i in range(n+1):
    m.append(m[-1]-a[i+1][0]+a[i][0]+a[i+1][1])
    mb.append(m[-2]-a[i+1][0]+a[i][0]+a[i+1][1]-a[i+1][0])
    h.append(h[-1]-a[-i-1][0]+a[-i-2][0]+a[-i-2][1])
    hb.append(h[-2]-a[-i-1][0]+a[-i-2][0]+a[-i-2][1]-c+a[-i-2][0])

mm=[0]
for i in range(n):
    mm.append(max(mm[-1],m[i+1]))
hm=[0]
for i in range(n):
    hm.append(max(hm[-1],h[i+1]))
    
ans=max(hm[-1],mm[-1])
for i in range(1,n):
    ans=max(hb[i]+mm[-i-1], mb[i]+hm[-i-1],ans)
print(ans)
# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter

# stdin = open("sample.txt")

h, w = [int(x) for x in stdin.readline().rstrip().split()]

if h == 1 or w == 1:
    print(1)
else:
    if h*w % 2 == 0:
        print(h*w // 2)
    else:
        print((h*w + 1) // 2)

### FIXED CODE ###

from sys import stdin
# stdin = open("sample.txt")

a = int(stdin.readline().rstrip())

b = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(b[a-1])
S = input()
if S[0] == S[1] and s[1] == S[2]:
  print("No")
else:
  print("Yes)

### FIXED CODE ###

S = input()
if S[0] == S[1] and S[1] == S[2]:
  print('No')
else:
  print('Yes')
N=input()
if N==1:
  	print "Hello World"
else:
  	A=input()
    B=input()
   	print A+B

### FIXED CODE ###

N=input()
if N==1:
	print "Hello World"
else:
	A=input()
	B=input()
	print A+B
import numpy as np
n, k = map(int, input().split())
a = list(map(int, input().split()))
x, y = 0, 0
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            x += 1
        if (i < j) and (a[i] > a[j]):
            y += 1
num_np = np.array(num)
sum_left = sum(num_np[:,0])
sum_right = sum(num_np[:,1])
output = (x * k) % 1000000007 + (y * k * (k - 1) // 2) % 1000000007
print(output % 1000000007)

### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
a = list(map(int, input().split()))
x, y = 0, 0
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            x += 1
        if (i < j) and (a[i] > a[j]):
            y += 1

output = ((x * k * (k - 1) // 2) + (y * k)) % 1000000007
print(output)
;

### FIXED CODE ###

a,b,c=map(int,input().split())
print("YES") if b-a==c-b else print("NO")
a = input()
b = input()
aa = [s for s in a]
bb = [s for s in b]
na = len(a)
nb = len(b)

dp = [[0]*(nb) for _ in range(na)]
k = 0
for i in range(na):
    if a[i] == b[0]:
        k = 1
    dp[i][0] = k
k = 0
for i in range(nb):
    if b[i] == a[0]:
        k = 1
    dp[0][i] = k

for i in range(1, na):
    for j in range(1, nb):
        if a[i] == b[j]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

ans = []
x = na-1
y = nb-1
while x != 0 or y != 0:
    if x-1 == 0 and dp[x][y] == dp[x-1][y]+1:
        ans.append(a[x])
        x = x-1
    elif y-1 == 0 and dp[x][y] == dp[x][y-1]+1:
        ans.append(b[y])
        y = y-1
    elif x-1 > 0 and dp[x][y] == dp[x-1][y]:
        x = x-1
    elif y-1 > 0 and dp[x][y] == dp[x][y-1]:
        y = y-1
    else:
        ans.append(a[x])
        x = x-1
        y = y-1

print("".join(ans[::-1]))


### FIXED CODE ###

a = input()
b = input()
na = len(a)
nb = len(b)

dp = [[0]*(nb+1) for _ in range(na+1)]

for i in range(na):
    for j in range(nb):
        if a[i] == b[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
ans = []
num = dp[na][nb]
x = na
y = nb
while num:
    if dp[x][y] == dp[x-1][y]:
        x -= 1
    elif dp[x][y] == dp[x][y-1]:
        y -= 1
    else:
        ans.append(a[x-1])
        x -= 1
        y -= 1
        num -= 1

print("".join(ans[::-1]))
a = list(map(str, input().split()))
if a[1] == “+”:
	print(int(a[0]) + int(a[2]))
else:
	print(int(a[0]) - int(a[2]))


### FIXED CODE ###

a = list(map(str, input().split()))
if a[1] == "+":
  print(int(a[0]) + int(a[2]))
else:
  print(int(a[0]) - int(a[2]))
import sys
import bisect
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

MOD = 10 ** 9 + 7

if N < M:
    N, M = M, N
    S, T = T, S

idxs = {}
for n in range(10):
    arr = [i for i, x in enumerate(S) if x == n]
    idxs[n] = arr


@lru_cache(maxsize=None)
def solve(i, j):
    arr1 = S[i:]
    arr2 = T[j:]

    if len(arr1) == 0 or len(arr2) == 0:
        return 1

    ans = 0
    t = arr2[0]

    t_idxs = idxs[t]
    l = bisect.bisect_left(t_idxs, i)
    # print(idxs)

    for idx in t_idxs[l:]:
        ans += solve(idx + 1, j + 1)
        ans %= MOD

    ans += solve(i, j + 1)
    ans %= MOD

    #print("i,j,ans", i, j, ans)

    return ans


r = solve(0, 0)

print(r)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

MOD = 10 ** 9 + 7

dp = [[0] * (M+1) for _ in range(N+1)]
dp_cum = [[0] * (M+1) for _ in range(N+1)]

for x in range(N):
    for y in range(M):
        if S[x] == T[y]:
            dp[x + 1][y + 1] += dp_cum[x][y] + 1
            dp[x + 1][y + 1] %= MOD

        dp_cum[x + 1][y + 1] = (dp_cum[x+1][y] % MOD) \
            + (dp_cum[x][y + 1] % MOD) \
            - (dp_cum[x][y] % MOD) \
            + (dp[x + 1][y + 1] % MOD)

        dp_cum[x + 1][y + 1] %= MOD

        #print("---x,y", x, y, "----")
        #print("dp:", dp)
        #print("dp_cum", dp_cum)


ans = dp_cum[N][M] + 1
print(ans)
from collections import deque
n , m = map(int, input().split())
keys = deque()
def trans(k):
    res = [0 for i in range(n)]
    for i in k:
        res[-i] = 1
    res = int("".join(map(str, res)), 2)
    return res

for i in range(m):
    a, b = list(map(int, input().split()))
    c = deque(list(map(int, input().split())))
    keys.append(deque([a]) + c)
inf = 10 ** 8
dp = [inf for i in range(2**n)]
dp[0] = 0
for i in range(m):
    key_value = keys[i-1].popleft()
    can_open = keys[i-1]
    for j in range(2**n):
        next = j | trans(can_open)
        dp[next] = min(dp[next], dp[j] + key_value)
#print(dp)
if dp[-1] >= inf:
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

from collections import deque
n , m = map(int, input().split())
keys = deque()
def trans(k):
    res = [0 for i in range(n)]
    for i in k:
        res[-i] = 1
    res = int("".join(map(str, res)), 2)
    return res

for i in range(m):
    a, b = list(map(int, input().split()))
    c = deque(list(map(int, input().split())))
    c.appendleft(a)
    keys.append(c)
inf = 10 ** 8
dp = [inf for i in range(2**n)]
dp[0] = 0
for i in range(m):
    key_value = keys[i].popleft()
    can_open = keys[i]
    p = trans(can_open)
    for j in range(2**n):
        next = j | p
        dp[next] = min(dp[next], dp[j] + key_value)
#print(dp)
if dp[-1] >= inf:
    print(-1)
else:
    print(dp[-1])
n=int(input())
a=list(map(int, input().split()))

l=[0]*8

for i in range(n):
  if a[i]<399:
    l[0]="t"
  elif a[i]<799:
    l[1]="t"
  elif a[i]<1199:
    l[2]="t"
  elif a[i]<1599:
    l[3]="t"
  elif a[i]<1999:
    l[4]="t"
  elif a[i]<2399:
    l[5]="t"
  elif a[i]<2799:
    l[6]="t"
  elif a[i]<3199:
    l[7]="t"
  else:
    l[8]+=1
countt=l.count("t")

if countr==0:
  print(countt,countt)
else:
  print(max(0,countt-l[8]),min(countt+1,8))

### FIXED CODE ###

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

l=[0]*9

for i in range(n):
  if a[i]<400:
    l[0]="t"
  elif a[i]<800:
    l[1]="t"
  elif a[i]<1200:
    l[2]="t"
  elif a[i]<1600:
    l[3]="t"
  elif a[i]<2000:
    l[4]="t"
  elif a[i]<2400:
    l[5]="t"
  elif a[i]<2800:
    l[6]="t"
  elif a[i]<3200:
    l[7]="t"
  else:
    l[8]+=1
countt=l.count("t")

if l[8]==0:
  print(countt,countt)
else:
  print(max(countt,1),countt+l[8])
line = raw_input().split()
a = line[0]
b = line[1]

if a > 8 or b > 8:
    return ':('
else:
    return 'Yay!'

### FIXED CODE ###

line = input().split(' ')
a = line[0]
b = line[1]

if int(a) > 8 or int(b) > 8:
    print(':(')
else:
    print('Yay!')
N = int(input())
N = N - 1
#N = 100
a = []
s = ""

while N != 0:
    a.insert(0, N % 26)
    N = N //26

#print(a)

for i in range(0, len(a)-1):
    a[i] = chr(96+a[i])
    s += a[i]

s += chr(97+a[len(a)-1])

print(s)


### FIXED CODE ###

N = int(input())

s = ""
for i in range(12):
    if 26*(26**i-1)/25 < N and N <= 26*(26**(i+1)-1)/25:
        t = i#桁数-1
        break

#print(t + 1)
N = int(N - 26*(26**t-1)/25 - 1)

a = [0] * (t + 1)

for i in range(t + 1):
    a[t - i] = N%26
    N = N //26

#print(a)

for i in range(0, len(a)):
    a[i] = chr(97+int(a[i]))
    s += a[i]

#s += chr(97+a[len(a)-1])

print(s)
n.l = map(int,input().split())
al = [l+i for i in range(n)]
a = min(al,key=abs)
al.remove(a)
print(sum(al))

### FIXED CODE ###

n,l = map(int,input().split())
taste = [l+i for i in range(n)]
eat = min(taste,key = abs)
taste.remove(eat)
print(sum(taste))
N,X = map(int,input().split())
x = list(map(int,input().split()))
x.sort()
L = []
if (len(x) == 1):
  print(abs(X-x[0]))
else:
  for k in range(len(x)):
    L.append(abs(X-x[k]))
    L.sort()
print(L[0])

### FIXED CODE ###

N,X = map(int,input().split())
L = list(map(int,input().split()))
for i in range(N):
  L[i] = abs(L[i]-X)
L.sort()
L.reverse()
def gcd(a,b):
  if b == 0:
    return a
  else:
    return gcd(b,a%b)
def listgcd(L):
  p = L[0]
  for i in range(1,N):
    p = gcd(p,L[i])
  return p
if len(L) >= 2:
  print(listgcd(L))
else:
  print(L[0])
N, K = map(int, input().split())
items = []
neta = {}
for _ in range(N):
    t, d = tuple(map(int, input().split()))
    items.append((t, d))

    if t not in neta:
        neta[t] = d
    else:
        tmp = neta[t]
        if d > tmp:
            neta[t] = d

neta = sorted(neta.items(), key=lambda x:-x[1])
items = sorted(items, key=lambda x: -x[1])


ans1 = 0
select1 = set()
for i in range(K):
    t, d = items[i]
    select1.add(t)
    ans1 += d
ans1 += len(select1) ** 2


ans2 = 0
select2 = set()
cnt = 0
for k, v in neta:
    cnt += 1
    select2.add(k)
    ans2 += v
    if cnt == K:
        ans2 += cnt ** 2
        print(max(ans1, ans2))
        exit()

remain = K - cnt
i = 1
sel = set()
while remain != 0:
    t, d = items[i]
    if t not in sel:
        ans2 += d
        sel.add(t)
    else:
        i += 1
        sel.add(t)
print(max(ans1, ans2))


### FIXED CODE ###

N, K = map(int, input().split())
umai = {}
mazui = []
for _ in range(N):
    t, d = map(int, input().split())
    if t not in umai:
        umai[t] = d
    else:
        tmp = umai[t]
        if tmp < d:
            umai[t] = d
            mazui.append((t, tmp))
        else:
            mazui.append((t, d))

umai = sorted(umai.items(), key=lambda x: -x[1])
mazui = sorted(mazui, key=lambda x: -x[1])


umai_len = len(umai)
mazui_len = len(mazui)

acc_umai = [0 for _ in range(umai_len)]
acc_umai[0] = umai[0][1]
for i in range(umai_len - 1):
    acc_umai[i + 1] = acc_umai[i] + umai[i + 1][1]

acc_mazui = [0 for _ in range(mazui_len)]
if mazui_len > 0:

    acc_mazui[0] = mazui[0][1]
    for i in range(mazui_len - 1):
        acc_mazui[i + 1] = acc_mazui[i] + mazui[i + 1][1]
acc_mazui.insert(0, 0)

ans = []
for i in range(1, K + 1):
    if umai_len < i or mazui_len < K - i:
        continue
    ans.append(acc_umai[i - 1] + acc_mazui[K - i] + i ** 2)
print(max(ans))