Harryxun/stf_run huggingface dataset:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])

def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]

def resolve():
    N, M = map(int, input().split())
    G = np.zeros((N + 1, N + 1), dtype=np.int64)

    for _ in range(M):
        x, y = map(int, input().split())
        G[x, y] += 1
        G[y, x] += 1
    csr = csr_matrix(G)
    dist, pred = dijkstra(csgraph=csr ,return_predecessors=True)

    ok = False
    for i in range(2, N+1):
        ans = get_path(i, 1, pred)
        if len(ans)<1:
            print("No")
            return
        else:
            if ok == False:
                print("Yes")
                ok = True
            print(ans[1])

if __name__ == "__main__":
    resolve()

### FIXED CODE ###


from collections import deque
def resolve():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(lambda x:int(x)-1, input().split())
        G[x].append(y)
        G[y].append(x)

    dist = [-1]*N
    ans = [0]*N
    q = deque()
    q.append(0)
    while q:
        fm = q.popleft()
        for to in G[fm]:
            if dist[to] != -1:
                continue
            dist[to] += 1
            ans[to] = fm
            q.append(to)

    print("Yes")
    for i in range(1, N):
        print(ans[i] + 1)
        
if __name__ == "__main__":
    resolve()
pi = 3.141592653589

r = float(input())

print("{.5f} {.5f}".format(r*r*pi,2*pi*r))


### FIXED CODE ###


pi = 3.141592653589

r = float(input())

print(r*r*pi,2*pi*r)
N=int(input())
if N%2==0:
    s=N/2
    print(int(s*(N-1)))
if N%2==1:
    s=(N-1)/2
    print(int(s*N))

### FIXED CODE ###

S=input()
T=input()

ans=0
if S[0]==T[0]:ans+=1
if S[1]==T[1]:ans+=1
if S[2]==T[2]:ans+=1

print(ans)
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def paint_col(adj, cols, i, col):
    nxt = [i]

    while nxt:
        u = nxt[-1]
        try:
            v = next(adj[u])
            if cols[v] == 0:
                cols[v] = col
                nxt.append(v)
        except StopIteration:
            nxt.pop()
            cols[u] = col

def solve():
    n, m = map(int, sys.stdin.readline().split())
    adj = [[] for i in range(n)]

    for i in range(m):
        s, t = map(int, sys.stdin.readline().split())
        adj[s].append(t)
        adj[t].append(s)

    cols = [0] * n
    col = 1
    adj = list(map(iter, adj))

    for i in range(n):
        if cols[i] == 0:
            paint_col(adj, cols, i, col)
            col += 1

    debug(cols, locals())

    q = int(sys.stdin.readline())

    for i in range(q):
        s, t = map(int, sys.stdin.readline().split())

        if cols[s] == cols[t]:
            ans = 'yes'
        else:
            ans = 'no'

        print(ans)

if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def paint_col(adj, cols, i, col):
    nxt = [i]

    while nxt:
        u = nxt[-1]
        try:
            v = next(adj[u])
            if cols[v] == 0:
                cols[v] = col
                nxt.append(v)
        except StopIteration:
            nxt.pop()
            cols[u] = col

def solve():
    n, m = map(int, sys.stdin.readline().split())
    adj = [[] for i in range(n)]

    for i in range(m):
        s, t = map(int, sys.stdin.readline().split())
        adj[s].append(t)
        adj[t].append(s)

    cols = [0] * n
    col = 1
    adj = list(map(iter, adj))

    for i in range(n):
        if cols[i] == 0:
            paint_col(adj, cols, i, col)
            col += 1

    # debug(cols, locals())

    q = int(sys.stdin.readline())

    for i in range(q):
        s, t = map(int, sys.stdin.readline().split())

        if cols[s] == cols[t]:
            ans = 'yes'
        else:
            ans = 'no'

        print(ans)

if __name__ == '__main__':
    solve()
n = int(input())
a = 0
while 10 ** a < n:
    a = a + 1
b = n // (10 ** (a -1))
c = b * (10 ** (a - 1)) - 1
d = 0
for i in range(len(str(c))):
    d = d + int(str(c)[i])
print(d)

### FIXED CODE ###

n = int(input())
a = 0
while 10 ** a <= n:
    a = a + 1
b = (n + 1) // (10 ** (a -1))
c = b * (10 ** (a - 1)) - 1
d = 0
for i in range(len(str(c))):
    d = d + int(str(c)[i])
print(d)
N = int(input())
S = input()
num = []

for i in range(N):
    East = S[:i]
    West = S[(i+1):]
    num.append(S[:i].count("W")+S[(i+1)].count("E"))
print(min(num))


### FIXED CODE ###

N = int(input())
S = input()
east = S.count("E")
west = 0
min = east

for i in S:
    if i == "E":
        east -= 1
    else:
        west += 1
    if min > east + west:
        min = east + west

print(min)
N=int(input())
a=list(map(int,input().split()))
ans=1
l=[0,0,0]
mod=10**9+7
for i in range(N):
  ans*=(l.count(a[i]))
  index=l.index(a[i])
  l[index]+=1
print(ans%mod)

### FIXED CODE ###

import sys
N=int(input())
a=list(map(int,input().split()))
ans=1
l=[0,0,0]
mod=10**9+7
for i in range(N):
  ans*=(l.count(a[i]))
  if a[i] not in l:
    print(0)
    sys.exit()
  index=l.index(a[i])
  l[index]+=1
print(ans%mod)
n = int(raw_input())
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
X = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
col = [0 for i in range(n)]
t = [0]
 
def DFS_visit(u):
    col[u] = 1
    t[0] += 1
    d[u] = t[0]
    for v in range(n):
        if M[u][v] == 1 and col[v] == 0:
            DFS_visit(v)
    clo[u] = 2
    t[0] += 1
    f[u] = t[0]
 
def DFS():
    for u in range(n):
        if col[u] == 0:
            DFS_visit(u)
    for u in range(n):
        print'{0} {1} {2}'.format(s+1, d[s], f[s])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()

### FIXED CODE ###

n = int(raw_input())
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
G = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
col = [0 for i in range(n)]
t = [0]
 
def DFS_visit(u):
    col[u] = 1
    t[0] += 1
    d[u] = t[0]
    for v in range(n):
        if M[u][v] == 1 and col[v] == 0:
            DFS_visit(v)
    col[u] = 2
    t[0] += 1
    f[u] = t[0]
 
def DFS():
    for u in range(n):
        if col[u] == 0:
            DFS_visit(u)
    for u in range(n):
        print'{0} {1} {2}'.format(u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()
str = input()
a = str[0]
b = str[2]
print(a*b, end='')
print((a+b)*2)

### FIXED CODE ###

x=str(input())
n=x.split(" ", 2)
a=int(n[0])
b=int(n[1])
ab=a*b
a_b=(a+b)*2
print(ab, end=' ')
print(a_b)
n = int(input())
xy = []
renso = {}
ans = []

for i in range(n):
    xin,yin = map(int,input().split())
    xy.append((xin,yin))

xy.sort(key=lambda x:x[1])
xy.sort(key=lambda x:x[0])

for i in range(n):
    for j in range(i,n):
        if( i==j ):
            continue
        t = (xy[i][0]-xy[j][0],xy[i][1]-xy[j][1])
        ans.append(t)

res = [ans.count(e) for e in set(ans)]
print(n-max(res))

### FIXED CODE ###

n = int(input())
xy = []
ans = []

for i in range(n):
    xin,yin = map(int,input().split())
    xy.append([xin,yin])

if n==1:
    print(1)
    exit(0)

xy.sort(key=lambda x:x[1])
xy.sort(key=lambda x:x[0])

for i in range(n):
    for j in range(n):
        if( i==j ):
            continue
        t = (xy[i][0]-xy[j][0],xy[i][1]-xy[j][1])
        ans.append(t)

res = [ans.count(e) for e in set(ans)]
print(n-max(res))
import bisect
N = int(input())
S = str(input())

S = list(S)

number_place_dict={}
for i in range(10):
  number_place_dict[i]=list()

#print(number_place_dict)

for i in range(len(S)):
  number_place_dict[int(S[i])].append(i)

#print(number_place_dict)

ans = 0

for i in range(0,1000):
  i = list(str(i))
  if len(i) == 1:
    i = [00]+i
  elif len(i) == 2:
    i = [0]+i
  
  #print(i)

  next_place_confition = -1

  for j in range(0,3):
    #print("数字:",int(i[j]),end="")
    place_list = number_place_dict[int(i[j])]
    index = bisect.bisect_right(place_list, next_place_confition)
    if index == len(place_list):
      #print("条件合致無し")
      break
    else:
      next_place_confition = place_list[index]
      #print("……次は→以上のindexが要:",next_place_confition)
  else:
    #print("OK")
    ans += 1

print(ans)

### FIXED CODE ###

import bisect
N = int(input())
S = str(input())

S = list(S)
#print(S)

number_place_dict={}
for i in range(10):
  number_place_dict[i]=list()

#print(number_place_dict)

for i in range(len(S)):
  #print(int(S[i]))
  number_place_dict[int(S[i])].append(i)

#print(number_place_dict)

ans = 0

for i in range(0,1000):
  i = list(str(i))
  if len(i) == 1:
    i = [0] + [0] + i
  elif len(i) == 2:
    i = [0] + i
  elif len(i) == 0:
    i = [0] + [0] + [0]
  
  #print("i;",i)

  next_place_confition = -1

  for j in range(0,3):
    #print("数字:",int(i[j]),end="")
    place_list = number_place_dict[int(i[j])]
    index = bisect.bisect_right(place_list, next_place_confition)
    if index == len(place_list):
      #print("条件合致無し")
      break
    else:
      next_place_confition = place_list[index]
      #print("……次は→以上のindexが要:",next_place_confition)
  else:
    #print("OK")
    ans += 1

print(ans)
from collections import deque
N = int(input())
alpha = ['a','b','c','d','e','f','g','h','i','j']
ans = []

stack = deque(['a'])

while stack:
    print(stack)
    if len(stack[-1]) == N:
        break
    s = stack.pop()
    s_list = list(s)
    index = alpha.index(s_list[-1])
    print(index)
    for i in range(index+2):
        stack.appendleft(s+alpha[i])
    

stack.reverse()
for j in range(len(stack)):
    print(stack[j])



### FIXED CODE ###

from collections import deque
N = int(input())
alpha = ['a','b','c','d','e','f','g','h','i','j']
ans = []

stack = deque(['a'])

while stack:
    if len(stack[-1]) == N:
        break
    s = stack.pop()
    s_list = sorted(list(s))
    index = alpha.index(s_list[-1])
    for i in range(index+2):
        stack.appendleft(s+alpha[i])
    

stack.reverse()
for j in range(len(stack)):
    print(stack[j])
from functools import reduce
from math import gcd

n = int(input())
a = [int(i) for i in input().split()]
ans = -1
for i in range(1,n+1):
    ans = max(ans,reduce(gcd,a[:i-1]+a[i:]))
print(ans)


### FIXED CODE ###

from fractions import gcd

n = int(input())
a = [int(i) for i in input().split()]

l = [0]
r = [0]
for i in range(n-1):
    l.append(gcd(l[i],a[i]))
    r.append(gcd(r[i],a[-1-i]))

m = 0
for i in range(n):
    m = max(m,gcd(l[i],r[-i-1]))

print(m)
n,d=map(int,input().split())
print(ceil(n/(2*d+1)))


### FIXED CODE ###

from math import *
n,d=map(int,input().split())
print(ceil(n/(2*d+1)))
a,b,c=map(int, input().split())
if a-b>=c:
  print(0)
else:
  print(c-a+b

### FIXED CODE ###

a,b,c=map(int, input().split())
if a-b>=c:
  print(0)
else:
  print(c-a+b)
s=input()
print(int(s[0])+int(s[1])+int(s[2])

### FIXED CODE ###

s=str(input())
print(int(s[0])+int(s[1])+int(s[2]))
s=input()
print(s-"FESTIVAL")

### FIXED CODE ###

s=input()
print(s[:-8])
L,R=(int(x) for x in input().split())
L_mod=L%2019
R_mod=R%2019
if L_mod>=R_mod:
    print(0)
else:
    print(L_mod*(L_mod+1s))


### FIXED CODE ###

L,R=(int(x) for x in input().split())
ans=[]
for n in range(2019):
    if L+n>=R:
        break
    for l in range(n+1,2019):
        if L+l>R:
            break
        a=(L+n)%2019
        b=(L+l)%2019
        c=a*b%2019
        ans.append(c)
print(min(ans))
o = input()
e = input()
a = ''
O = len(o)
E = len(e)
if O == E:
    for i in range(O):
        a += o[i]
        a += e[i]
    print(a)
else:
    for i in range(O-1):
        a += o[i]
        a += e[i]
    a += o[O]
    print(a)

### FIXED CODE ###

o = input()
e = input()
a = ''
O = len(o)
E = len(e)
if O == E:
    for i in range(O):
        a += o[i]
        a += e[i]
    print(a)
else:
    for i in range(O-1):
        a += o[i]
        a += e[i]
    a += o[O-1]
    print(a)
import numpy as np
firstline=input().split()
K=int(firstline[0])
X=int(firstline[1])
blackstone=np.arange(X-K+1,X+K)
array_info(blackstone)

### FIXED CODE ###

line = input().split()
K = int(line[0])
X = int(line[1])

ans = list(range(X-K+1,X+K))
print(' '.join(map(str,ans)))
H, W = map(int, input().split())
graph = []
for _ in range(H):
    graph.append(list(input()))

res = True

for i in range(1, W-1):
    for j in range(1, H-1):
        if graph[i][j] == '#' and graph[i + 1][j] == '.' and graph[i - 1][j] == '.' and graph[i][j + 1] == '.' and graph[i][j - 1] == '.':
            res = False
            break
    if not res:
        break
print('Yes' if res else 'No')


### FIXED CODE ###

H, W = map(int, input().split())
graph = []
for _ in range(H):
    graph.append(list(input()))

res = True

for j in range(1, W-1):
    for i in range(1, H-1):
        if graph[i][j] == '#' and graph[i + 1][j] == '.' and graph[i - 1][j] == '.' and graph[i][j + 1] == '.' and graph[i][j - 1] == '.':
            print('No')
            exit()
print('Yes')
n=int(input())
a=[]
b=[]
c=[]
a=list(map(int,input().split()))


for i in range(n):

    if a[i]%2==0:
        b.append(a[i])

    else:pass


for k in range(len(b)):

    if b[k]%3==0 or b[k]%5==0:

        c.append(b[k])

if len(b)==len(c):

    print("APPROVED")

else:
    print("DENIED")


### FIXED CODE ###

a=[]
a=list(map(int,input().split()))
a=set(a)

if len(a)==2:

    print("Yes")

else:print("No")
s=int(input())
h=s//3600
ss=(ss-3600*h)//60
se=(ss-3600*h-h*60)
print("{}:{}:{}".format(h,ss,se)

### FIXED CODE ###

s=int(input())
h=s//3600
ss=(s-3600*h)//60
se=(s-3600*h-ss*60)
print("{}:{}:{}".format(h,ss,se))
import math
a,b=map(int,input().split())
x=math.gcd(a,b)
print(a*b//x)

### FIXED CODE ###

import fractions
a,b=map(int,input().split())
x=fractions.gcd(a,b)
print(a*b//x)
a=int(input())
ans=0
for i in range(a):
  x=a//i
  ans+=((a+1)a)/2
print(ans)

### FIXED CODE ###

a=int(input())
b=(a)//2+1
ans=0
for i in range(1,b,1):
  x=a//i
  ans+=((x**2+x)//2)*i
ans+=(a**2+a+b-b**2)//2
print(ans)
```python
n = int(input())
print(n * (n - 1) // 2)
```


### FIXED CODE ###

n = int(input())
print((n + 1) * n // 2 - n)
N=int(input())
a=[list(map(int,input().split())) for i in range(N)]
flag=False
for cx in range(101):
    if flag:
        break
    for cy in range(101):
        if flag:
            break
        for i in range(N):
            if i==0 or H==0:
                H=a[i][2]+abs(cx-a[i][0])+abs(cy-a[i][1])
            if a[i][2]!=0 and H!=a[i][2]+abs(cx-a[i][0])+abs(cy-a[i][1]) and H!=0:
                break
            if i==N-1:
                x=cx
                y=cy
                flag=True
print(x,y,H)

### FIXED CODE ###

N=int(input())
a=[list(map(int,input().split())) for i in range(N)]
flag=False
for cx in range(101):
    if flag:
        break
    for cy in range(101):
        count=0
        if flag:
            break
        for i in range(N):
            if a[i][2]!=0:
                if count==0:
                    H=a[i][2]+abs(cx-a[i][0])+abs(cy-a[i][1])
                    count+=1
                if H!=a[i][2]+abs(cx-a[i][0])+abs(cy-a[i][1]):
                    break
            if i==N-1:
                x=cx
                y=cy
                flag=True
                for k in range(N):
                    if a[k][2]!=max(H-abs(x-a[k][0])-abs(y-a[k][1]),0):
                        flag=False
print(x,y,H)
import itertools
from collections import Counter

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

C=Counter(S)
r = C['R']
g = C['G']
b = C['B']


cnt = r * g * b

sum = 0
for i in range(0,N-2):
    for j in range(i,N-1):
        k = j + j - i
        if k < N
            if (S[i] != S[j]) and (S[i] != S[k] and S[j] != S[k]):
                cnt -= 1

print(cnt)


### FIXED CODE ###

import itertools
from collections import Counter

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

C=Counter(S)
r = C['R']
g = C['G']
b = C['B']


cnt = r * g * b

for i in range(0,N-2):
    for j in range(i,N-1):
        k = j + j - i
        if k < N:
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                cnt -= 1

print(cnt)
n = int(input())
A = list(map(int, input().split()))
B = []
C = []
for i in range(n):
    if i % 2 == 0:
        B.append(A[i])
    else:
        C.append(A[i])
if len(B) > len(C):
    print(*reversed(B), *C)
else:
    print(*reversed(C), *B)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
B = []
C = []
for i in range(n):
    if i % 2 == 0:
        B.append(A[i])
    else:
        C.append(A[i])
if len(B) > len(C):
    ans = list(reversed(B)) + C
    print(*ans)
else:
    ans = list(reversed(C)) + B
    print(*ans)
import fractions
# import math
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

n = int(input())
a = [int(value) for value in input().split(" ")]


a = sorted(a)

b = []
c = []

for value in a:
    if value % 2 != 0:
        b.append(value)
    else:
        c.append(value)

if len(b) == 0:
    a.remove(c[0])
    print(gcd_list(a))
else:
    a.remove(b[0])
    print(gcd_list(a))

### FIXED CODE ###

i = input().split(" ")
a=int(i[0])
b=int(i[1])
t=int(i[2])
print(t // a * b)
A₁,A₂,A₃=map(int,input().split())

if A₁+A₂+A₃>=22:
  print('bust')
else:
  print('win')

### FIXED CODE ###

A1,A2,A3=map(int,input().split())

if A1+A2+A3>=22:
  print('bust')
else:
  print('win')
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.par[x]
        y = self.par[y]
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, input().split())
p = [0] + [int(_) for _ in input().split()]
pair = [[int(_) for _ in input().split()] for _ in range(M)]
uf = UnionFind(N+1)
ans = 0

for i in pair:
    uf.union(i[0], i[1])

for i in range(1, N+1):
    if uf.find(i) == uf.find(p[i]):
        ans += 1

print(ans)

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, input().split())
p = [0] + [int(_) for _ in input().split()]
pair = [[int(_) for _ in input().split()] for _ in range(M)]
uf = UnionFind(N+1)
ans = 0

for i in pair:
    uf.union(i[0], i[1])

for i in range(1, N+1):
    if uf.find(i) == uf.find(p[i]):
        ans += 1

print(ans)
x = (input())
print(x*x*x)

### FIXED CODE ###

print(int(input())**3)
a = map(int,input().split())
a.sort()
print(a[2]-a[0])

### FIXED CODE ###

a = list(map(int,input().split()))
print(max(a) - min (a))
from collections import deque
h, w = map(int, input().split())
mass = [[ord(i) for i in input().split()]for _ in range(h)]
wall = ord("#")
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(s, t):
    if mass[s][t] == wall:
        return 0
    visited = [[0] * w for _ in range(h)]
    depth = [[0] * w for _ in range(h)]
    q1 = deque([s])
    q2 = deque([t])
    while q1:
        x = q1.popleft()
        y = q2.popleft()
        visited[x][y] += 1
        r = depth[x][y] + 1
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == wall:
                continue
            if visited[nx][ny]:
                continue

            q1.append(nx)
            q2.append(ny)
            depth[nx][ny] = r

    u = 0
    for row in depth:
        u = max(u, max(row))
    return u


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))



### FIXED CODE ###

import numpy as np
from collections import deque
h, w = map(int, input().split())
r = [list(input()) for i in range(h)]


def dist(s, t):
    if r[s][t] == "#":
        return 0
    else:
        visited = np.zeros((h, w))
        visited[s][t] += 1
        distance = np.zeros((h, w))
        q = deque([[s, t]])
        while len(q) > 0:
            i, j = q.popleft()
            d = distance[i][j] + 1
            if j != w-1:
                if r[i][j+1] == "." and not visited[i][j+1]:
                    q.append([i, j + 1])
                    visited[i][j+1] += 1
                    distance[i][j+1] += d
            if j != 0:
                if r[i][j-1] == "." and not visited[i][j-1]:
                    q.append([i, j - 1])
                    visited[i][j - 1] += 1
                    distance[i][j - 1] += d
            if i != 0:
                if r[i-1][j] == "." and not visited[i-1][j]:
                    q.append([i - 1, j])
                    visited[i-1][j] += 1
                    distance[i-1][j] += d
            if i != h-1:
                if r[i+1][j] == "." and not visited[i+1][j]:
                    q.append([i + 1, j])
                    visited[i+1][j] += 1
                    distance[i+1][j] += d
        return np.max(distance)


ans = 0
for s in range(h):
    for t in range(w):
        ans = max(ans, dist(s, t))

print(int(ans))
while True:
 n, x = map(int(input().split()))
 if n == x == 0:
  break
 Sum = 0
 count = 0
 for a in range(1, n):
  for b in range(a + 1, n):
   for c in range(b + 1, n):
    Sum = a + b + c
    if Sum == x:
     count = count + 1
 print(count)

### FIXED CODE ###

while True:
 n, x = map(int, input().split())
 if n == x == 0:
  break
 Sum = 0
 count = 0
 for a in range(1, n + 1):
  for b in range(a + 1, n + 1):
   for c in range(b + 1, n + 1):
    Sum = a + b + c
    if Sum == x:
     count = count + 1
 print(count)
a = int(input()) #ch
b = int(input())  #ch
h = int(input())  #hour
m = int(input())  #minits

import math

angle = abs((30 * h + m * 0.5) - m*6)

if angle > 180:
    angle = 360 - angle
if ang==180:
  print(a+b)
elif(ang==0):
  print(abs(b - a)):
else:
cos = math.cos(math.radians(angle))
ans = (a * a) + (b * b) - (2 * a * b * cos)
print(math.sqrt(ans))



### FIXED CODE ###

import math

a, b, h, m = map(int, input().split())
h=h*60+m

ang=abs(h*0.5-m*6)
if ang > 180:
  ang = 360-ang
if ang==180:
  print(a+b)
elif(ang==0):
  print(abs(b-a))
else:
  ans=(a**2)+(b**2)-(2*a*b*math.cos(math.radians(ang)))
  print(math.sqrt(ans))
n, m, c = map(int, input().split())
l = (0,) + tuple(map(int, input().split()))
a = [0] * (c + 1)
w = [tuple(map(int, input().split())) for _ in range(n)]
w.sort(key = lambda x:x[1], reverse = True)
v = 0
p = 0
for i in range(n):
    if l[w[i][0]]:
        l[w[i][0]] -= 1
        v += w[i][1]
        p += 1
        if p == m:
            break
print(v)


### FIXED CODE ###

n, m, c = map(int, input().split())
l = [0] + list(map(int, input().split()))
w = [tuple(map(int, input().split())) for _ in range(n)]
w.sort(key = lambda x:x[1], reverse = True)
v = 0
p = 0
for i in range(n):
    if l[w[i][0]]:
        l[w[i][0]] -= 1
        v += w[i][1]
        p += 1
        if p == m:
            break
print(v)