Harryxun/stf_run huggingface dataset:
n,m=map(int,input().split())
X = [list(map(int,input().split())) for i in range(m)]
a_list = []
b_list = []
for i in range(m):
  if X[i][0] = 1:
    a_list.append(X[i][1])
  elif X[i][1] = 1:
    a_list.append(X[i][0])
  elif X[i][0] = n:
    b_list.append(X[i][1])
  elif X[i][1] = n:
    b_list.append(X[i][0])
c_dic = {a_list}&{b_list}
if len(c_dic) ==0:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

### FIXED CODE ###

n,m = map(int,input().split())
X = [list(map(int,input().split())) for i in range(m)]
a_list = []
b_list = []
for i in range(m):
  if X[i][0] == 1:
    a_list.append(X[i][1])
  elif X[i][1] == n:
    b_list.append(X[i][0])
c_set = set(a_list) & set(b_list)
if len(c_set) ==0:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    w, h, n = map(int, input().split())
    px = py = 0
    points = [[px, py], [w, h]]
    for _ in range(n):
        x, y, a = map(int, input().split())
        if a == 1:
            points[0][0] = max(px, x)
        elif a == 2:
            points[1][0] = min(w, x)
        elif a == 3:
            points[0][1] = max(py, y)
        elif a == 4:
            points[1][1] = min(h, y)

    print(max(0, points[1][0]-points[0][0])) * max(0, points[1][1]-points[0][1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    w, h, n = map(int, input().split())
    px = py = 0
    for _ in range(n):
        x, y, a = map(int, input().split())
        if a == 1:
            px = max(px, x)
        elif a == 2:
            w = min(w, x)
        elif a == 3:
            py = max(py, y)
        elif a == 4:
            h = min(h, y)

    print(max(0, w-px) * max(0, h-py))


if __name__ == '__main__':
    main()
#print("Enter Number")
a = int(input())
b = int(input())

i = a * b
if i % 2 == 0:
    print("Even")
else:
    print("Odd")


### FIXED CODE ###

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

i = s[0] * s[1]
if i % 2 == 0:
    print("Even")
else:
    print("Odd")
K = int(input())
A = int(input())
B = int(input())
""" K=7
A=500
B=600 """


if A==B:
    if A%K==0:
        print("OK")
    else:
        print("NG")

num=A
while num <= B:
    num += 1
    if num%K == 0:
        print("OK") 
        break
    if num==B:
        print("NG")
        break



### FIXED CODE ###

k=int(input())
a,b= map(int, input().split())
q=0
 
for i in range(1,1000):
  if a<=k*i and k*i<=b:
    print('OK')
    q=1
    break
 
if q==0:
  print('NG')
N,M=map(int,input().split())
print(N*(N-1)//2+M*(M-1)//2)

S=input()
T=S[:(len(S)-1)//2-1]
U=S[(len(S)+3)//2-1:]
if S==S[::-1]:
    if T==T[::-1]:
        if U==U[::-1]:
            print('Yes')
        else:print('No')
    else:print('No')
else:print('No')


### FIXED CODE ###

S=input()
T=S[:(len(S)-1)//2]
U=S[(len(S)+3)//2-1:]
if S==S[::-1]:
    if T==T[::-1]:
        if U==U[::-1]:
            print('Yes')
        else:print('No')
    else:print('No')
else:print('No')
import numpy as np
def main(a,b):
    g = np.gcd(a,b)
    lcm = (x * y) // g
    return lcm

a,b = map(int,input().split())
print(main(a,b))

### FIXED CODE ###

import fractions
def main(a,b):
    g = fractions.gcd(a,b)
    lcm = (a * b) // g
    return lcm
    
a,b = map(int,input().split())
print(main(a,b))
import collections

rl = sys.stdin.readline

n = int(rl())

li = []
for _ in range(n):
    li.append(rl().rstrip())
c = collections.Counter(li)
max_cnt = 0
li = []
for k, v in c.items():
    if v < max_cnt:
        continue
    elif v == max_cnt:
        li.append(k)
    else:
        max_cnt = v
        li = [k]
li.sort()
print('\n'.join(li))





### FIXED CODE ###

import sys
import math
import itertools
import numpy
import collections

rl = sys.stdin.readline

n = int(rl())

li = []
for _ in range(n):
    li.append(rl().rstrip())
c = collections.Counter(li)
max_cnt = 0
li = []
for k, v in c.items():
    if v < max_cnt:
        continue
    elif v == max_cnt:
        li.append(k)
    else:
        max_cnt = v
        li = [k]
li.sort()
for i in li:
    print(i)
l=list(int(input()) for _ in range(5))
m=int(input())
cnt=0
for i in range(5):
  if l[i+1]-l[i]<=m:
    cnt+=1
print([":(","Yay!"][cnt==5])

### FIXED CODE ###

l=list(int(input()) for _ in range(5))
m=int(input())
print([":(","Yay!"][l[4]-l[0]<=m])
r = int(input())
print(3*a*a)

### FIXED CODE ###

r = int(input())
print(3*r*r)
s = input()
print(s-"FESTIVAL")

### FIXED CODE ###

s = input()
print(s[:len(s)-8])
def solve(a,w,dp):
    if not a or w==0: return 0
    if (str(a),w) in dp: return dp[(str(a),w)]
    maxx=0
    for i in range(len(a)):
        if a[i][0]<=w:
            maxx=max(maxx,a[i][1]+solve(a[:i]+a[i+1:],w-a[i][0],dp))
    dp[(str(a),w)]=maxx
    return maxx
if __name__=='__main__':
    n,w=map(int,input().split())
    a=[]
    sw=0
    for i in range(n):
        p,q=map(int,input().split())
        a.append((p,q))
        sw+=a[-1][0]
    a.sort(key=lambda x: x[0])
    print(solve(a,w,{}))

### FIXED CODE ###

def solve(w,v,tv,W):
    dp=[float('inf')]*(tv+1)
    dp[0]=0
    for i in range(len(w)):
        for j in range(tv-v[i],-1,-1):
            dp[j+v[i]]=min(dp[j+v[i]],dp[j]+w[i])
    maxx=0
    for i in range(tv+1):
        if dp[i]<=W:
            maxx=max(maxx,i)
    return maxx
if __name__=='__main__':
    n,W=map(int,input().split())
    w=[]
    v=[]
    for i in range(n):
        p,q=map(int,input().split())
        w.append(p)
        v.append(q)
    print(solve(w,v,sum(v),W))
import math

a=int(input())

L = 2*math.pi*a
s = a*a*math.pi

print("%.6f"%(L),"%.6f"%(s))

### FIXED CODE ###

import math

n = float( input() )

L = 2*math.pi*n
S = n * n * math.pi

print("%.6f"%(S),"%.6f"%(L))
n, r = map(int, input().split())
d = []

while n > 0:
    d.append(n % k)
    n = n // k
    
print(len(d))

### FIXED CODE ###

n, k = map(int, input().split())
ans = 0
while n > 0:
    n = n // k
    ans += 1
print(ans)
# coding: utf-8
# Your code here!
import math

A,B,C,D=map(int,input().split())
A-=1
print(A)
num1=A-A//C-A//D+(A//(C*D//math.gcd(C, D)))
num2=B-B//C-B//D+(B//(C*D//math.gcd(C, D)))

print(num1)
print(num2)

print(num2-num1)

### FIXED CODE ###

# coding: utf-8
# Your code here!
A,B,C,D=map(int,input().split())
A-=1

def gcd(a,b):
    ans=1
    for i in range(1,int(min(a,b)**0.5)+1):
        
        if a%i==0 and b%i==0:
            ans=max(ans,i)
        temp=min(a,b)//i
        if a%temp==0 and b%temp==0:
            ans=max(ans,temp)
    return ans

num1=A-A//C-A//D+(A//(C*D//gcd(C, D)))
num2=B-B//C-B//D+(B//(C*D//gcd(C, D)))

print(num2-num1)
import numpy as np

n = int(input())

l = np.empty(n)
l[:] = np.nan

k = 0
i = 1

while i <= n:
  if n % i == 0:
    l[k] = i + (n // i) - 2
    k += 1
  i += 1
print(int(np.nanmin(l)))

### FIXED CODE ###

n = int(input())

for i in range(int(n ** 0.5)):
  if n % (int(n ** 0.5) - i) == 0:
    j = n // (int(n ** 0.5) - i)
    break
    
print(int(n ** 0.5) - i + j - 2)
s = input()
if(s[0]==s[1] and s[1]==s[2]):
    print("No")
else:
    print("Yes")

### FIXED CODE ###

s=input()
if s=='AAA' or s=='BBB':
    print('No')
else:
    print('Yes')
a=input()
list=["Sunny","Cloudy","Rainy"]
if a=list[0] or list[1]:
  print(list[a+1])
else:
  print(list[0])
    
  

### FIXED CODE ###

a=input()
if a=="Sunny":
  print("Cloudy")
elif a=="Cloudy":
  print("Rainy")
else:
  print("Sunny")
N,M = map(int, input().split())

PY_list = []
for num,i in enumerate(range(M)):
    p,y = map(int, input().split())
    PY_list = PY_list + [(num,p,y),]

rec = []
for i in range(N):
    cities = []
    for k in PY_list:
        if k[1] == i+1:
            cities = cities + [k,]
    cities = sorted(cities, key=lambda x:x[2])

    rec_list = []
    for num,k in enumerate(cities):
        rec_list = rec_list + [(k[0],str(k[1]).zfill(6) + str(num+1).zfill(6)),]

    rec = rec + rec_list
rec = sorted(rec, key=lambda x:x[0])

for s in rec:
    print(s[1])

### FIXED CODE ###

a,b = map(int, input().split())
print(a+(b//2))
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(0,n,2):
if a[i] % 2 == 1:
ans += 1
print(ans)

### FIXED CODE ###

x=int(input())
main=list(map(int,input().split()));count=0
for i in range(len(main)):
    if(main[i]%2!=0 and (i+1)%2!=0): count=count+1
print(count)
def main():
    n = int(input())
    if n == 1:
        print(0)
        return
    def eratos(n):
        flag = [True] * (n + 1)
        for i in range(2, int(n**0.5) + 1):
            if flag[i]:
                for j in range(2*i, n + 1, i):
                    flag[j] = False
        return [i for i, x in enumerate(flag) if x and i >= 2]
    p = eratos(10**6)
    work = []
    for i in p:
        piyo = 0
        while n % i == 0:
            n //= i
            piyo += 1
        if piyo > 0:
            work.append(piyo)
        if n == 1:
            break
    if len(work) == 0:
        print(1)
        break
    else:
        result = 0
        for i in work:
            for j in range(1, 10**6):
                i -= j
                if i <0:
                    break
                result += 1
    if n != 1:
        result += 1
    print(result)
main()

### FIXED CODE ###

def main():
    n = int(input())
    if n == 1:
        print(0)
        return
    def eratos(n):
        flag = [True] * (n + 1)
        for i in range(2, int(n**0.5) + 1):
            if flag[i]:
                for j in range(2*i, n + 1, i):
                    flag[j] = False
        return [i for i, x in enumerate(flag) if x and i >= 2]
    p = eratos(10**6)
    work = []
    for i in p:
        piyo = 0
        while n % i == 0:
            n //= i
            piyo += 1
        if piyo > 0:
            work.append(piyo)
        if n == 1:
            break
    if len(work) == 0:
        print(1)
        return
    else:
        result = 0
        for i in work:
            for j in range(1, 10**6):
                i -= j
                if i <0:
                    break
                result += 1
    if n != 1:
        result += 1
    print(result)
main()
import numpy as np
def knapsack(w,val,W,n,t):
    for i in range(1,n+1):
        for j in range(1,W+1):
            if w[i-1]<=j:
                t[i][j]=max(val[i-1]+t[i-1][j-w[i-1]],t[i-1][j])
            else:
                t[i][j]=t[i-1][j]
    return t[n][W]            
n,W=map(int,input().split())                
w=[]
val=[]
t=np.zeros([n+1,W+1],dtype=int)
for i in range(0,n):
    a,b=map(int,input().split())
    w.append(a)
    val.append(b)
ans=knapsack(w,val,W,n,t)
print(ans)
    

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
dp=[0]*(n+1)
h.insert(0,0)
dp[2]=abs(h[2]-h[1])
for i in range(3,n+1):
    dp[i]=min(abs(h[i]-h[i-1])+dp[i-1],abs(h[i]-h[i-2])+dp[i-2])
print(dp[n])
import copy
def dfs(cur_node, pre_node, Node_num, map, l):
    #全てのノードを見たとき

    if Node_num == N or cur_node <= 0 or cur_node >= N:
        return
    elif l[pre_node][cur_node]==0: #飛んだ先が、Trueの時
        return
    elif map[cur_node]==True:
        return

    map[cur_node]=True
    for i in range(N):
        if i != cur_node:
            dfs(i, cur_node, Node_num+1, map, l)


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

N = S[0]
M = S[1]


map = [False]*N
map[0] = True

lst = []

for i in range(M):
    lst.append([0]*N)

for i in range(M):
    S = input()
    S = list(S.split())
    idx1 = int(S[0])
    idx2 = int(S[1])
    lst[idx1-1][idx2-1] = 1
    lst[idx2-1][idx1-1] = 1


graph_count = 0
#全探索
for i in range(1, N, 1):
    map_copy = copy.copy(map)
    lst_copy = copy.copy(lst)

    dfs(i, 0, 0, map_copy, lst_copy)
    count = 0

    for i in map_copy:
        if i == True:
            count = count + 1
    if count == N:
        graph_count = graph_count + 1

print(graph_count)


### FIXED CODE ###

import itertools
N,M=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i in range(M)}
ans=0
for i in itertools.permutations(range(2,N+1),N-1):
    l=[1]+list(i)
    ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1
print(ans)
N = int(input())
b = list(map(int, input().split()))


def naive():
    # (1), (1,2), ..., (1,...,N)
    import itertools
    candidates = itertools.product(*[range(1, i + 1) for i in range(1, N+1)])
    for candidate in candidates:
        a = list()
        for j in candidate:
            a.insert(j-1, j)

        if a == b:
            return candidate
    
    return -1


def fast():
    candidate = list()
    
    while len(b) != 0:
        for i in range(len(b))[::-1]:
            if b[i] == (i+1):
                value = b.pop(i)
                candidate.append(value)
                break
            
        else:
            return -1

    candidate.reverse()
    return candidate
 
# print(naive())
# print(fast())
ans_list = fast()
for ans in ans_list:
    print(ans)


### FIXED CODE ###

N = int(input())
b = list(map(int, input().split()))


def fast():
    candidate = list()
    
    while len(b) != 0:
        for i in range(len(b))[::-1]:
            if b[i] == (i+1):
                value = b.pop(i)
                candidate.append(value)
                break
            
        else:
            return [-1]

    candidate.reverse()
    return candidate

ans_list = fast()
for ans in ans_list:
    print(ans)
#!/usr/bin/env python3
import sys
import numpy as np

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(H: int, W: int, s: "List[str]"):
    ans = YES
    for i in range(1, H-1):
        for j in range(1, W-1):
            if s[i][j] == "#" and s[i-1][j] == s[i+1][j] == s[i][j-1] == s[i][j+1] == ".":
                ans = NO
    print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(W)]  # type: "List[str]"
    solve(H, W, s)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(H: int, W: int, s: "List[str]"):
    ans = YES
    for i in range(1, H-1):
        for j in range(1, W-1):
            if s[i][j] == "#" and s[i-1][j] == s[i+1][j] == s[i][j-1] == s[i][j+1] == ".":
                ans = NO
    print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    H, W = map(int,input().split())  # type: int
    s = [input() for _ in range(H)]  # type: "List[str]"
    solve(H, W, s)

if __name__ == '__main__':
    main()
from functools import lru_cache

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

AB = []
for i in range(N):
  A, B = map(int, input().split())
  AB.append((A, B))

threshold = sum(a for a, b in AB)
bestA, bestB = max(AB, key=lambda ab: ab[0] / ab[1])

@lru_cache(maxsize=None)
def f(h):
    if h <= 0:
        return 0
    times = (h - threshold) // bestA
    if times > 0:
        return bestB * times + f(h - bestA * times)

    return min(b + f(h - a) for a, b in AB)

print(f(H))


### FIXED CODE ###

import sys
from functools import lru_cache

sys.setrecursionlimit(1000000)

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

AB = []
for i in range(N):
  A, B = map(int, input().split())
  AB.append((A, B))

'''
H = 10000
N = 1000
import random
AB = []
for i in range(N):
    A = random.randint(1, 10000)
    B = random.randint(1, 10000)
    AB.append((A, B))
'''




@lru_cache(maxsize=None)
def f(h):
    if h <= 0:
        return 0
    best = float('inf')
    for a, b in AB:
        val = b + f(h - a)
        if val < best:
            best = val
        else:
            break
    return best

AB.sort(key=lambda ab: (ab[0] / ab[1], -ab[0]), reverse=True)
bestA, bestB = AB[0]
threshold = sum(a for a, b in AB)

ans = None
times = (H - threshold) // bestA
if times > 0:
    ans = bestB * times + f(H - bestA * times)
else:
    ans = f(H)

print(ans)
def frog1(h):
    dp = [float('inf')]*3
    dp[0] = 0
    for i in range(1,len(h)):
        dp[i%3] = min([dp[(i-j)%3] + abs(h[i]-h[i-j]) for j in range(1,3)])
    return dp[(len(h)-1)%3]
    
n = input()
vals = map(int, input().split())

print(frog1(vals))

### FIXED CODE ###

def frog1(h):
    dp = [float('inf')]*3
    dp[0] = 0
    for i in range(1,len(h)):
        dp[i%3] = min([dp[(i-j)%3] + abs(h[i]-h[i-j]) for j in range(1,3)])
    return dp[(len(h)-1)%3]
    
n = input()
vals = list(map(int, input().split()))

print(frog1(vals))
def main():
    import sys
    input=sys.stdin.readline
    s=input()
    alpha="abcdefghijklmnopqrstuvwxyz"
    l=len(s)
    alpha2={j:i for i,j in enumerate(alpha)}
    memo=[[0]*26 for _ in range(l,-1,-1)]
    for i in range(26):
        memo[l][i]=l+1
    for i in range(l-1,-1,-1):
        for x,y in alpha2.items():  
            memo[i][y]=memo[i+1][y]
        memo[i][alpha2[s[i]]]=i+1
    search=[1]*(l+2)
    search[l+1]=0
    for i in range(l-1,-1,-1):
        m=max([memo[i][j] for j in range(26)])
        if m!=l+1:
            search[i]=search[m]+1
    
    n,seq=0,0
    ans_len=search[0]
    ans=""
    temp=0
    for i in range(ans_len):
        for j in range(26):
            n=memo[temp][j]
            seq=search[n]+i
            if seq+1==ans_len:
                ans+=alpha[j]
                temp=memo[temp][j]
                break
    print(ans)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input=sys.stdin.readline
    s=input()
    alpha="abcdefghijklmnopqrstuvwxyz"
    l=len(s)
    alpha2={j:i for i,j in enumerate(alpha)}
    memo=[[0]*26 for _ in range(l,-1,-1)]
    for i in range(26):
        memo[l][i]=l+1
    for x,y in alpha2.items():
        for i in range(l-1,-1,-1):
            if s[i]==x:
                memo[i][y]=i+1
            else:
                memo[i][y]=memo[i+1][y]
    
    search=[1]*(l+2)
    search[l+1]=0
    for i in range(l-1,-1,-1):
        m=max([memo[i][j] for j in range(26)])
        if m!=l+1:
            search[i]=search[m]+1
    
    n,seq=0,0
    ans_len=search[0]
    ans=""
    temp=0
    for i in range(ans_len):
        for j in range(26):
            n=memo[temp][j]
            seq=search[n]+i
            if seq+1==ans_len:
                ans+=alpha[j]
                temp=memo[temp][j]
                break
    print(ans)
if __name__=='__main__':
    main()
N,W = [int(i) for i in input().split()]
w = [] # limit weight to knapsack capacity
v = [] # maximize value
for i in range(N):
  line = input().split()
  w.append(int(line[0]))
  v.append(int(line[1]))
mem = [[0]*(W+1) for i in range(N)]
for i in range(w[0], W+1):
  mem[0][i] = v[0]
for i in range(1, N):
  for j in range(1, W+1):
    if w[i] > j:
      mem[i][j] = mem[i-1][j]
    else:
      mem[i][j] = max(mem[i-1][j], v[i] + mem[i-1][j - w[i]])
#print(mem)
print("%s" % mem[N-1][W])



### FIXED CODE ###

N, W = [int(i) for i in input().split()]
weight = []
value = []
for i in range(N):
  w, val = [int(i) for i in input().split()]
  weight.append(w)
  value.append(val)
# changing to value max as W_max ~ 10^9 and val_max ~= 1000 * next
val_max = 0
for i in range(N):
  val_max += value[i]
dp = [float('inf') for i in range(val_max+1)] # dp[i] is the min weight required for the value 
# hence our ans would be in the max value where the weight < knapsack weight
dp[0] = 0
for i in range(N):
  for v in range(val_max-value[i], -1, -1): # range of kanpsack weight in which i can push the current item
    dp[v + value[i]] = min(dp[v + value[i]], dp[v] + weight[i])
    #print(dp)
sol = 0
for i in range(val_max+1):
  if dp[i] <= W:
    sol = i
print("%s" % sol)
h, w = [int(i) for i in input().split()]
k = []
wl = []
  
for i in range(0, 10):
  k.append([int(i) for i in input().split()])
for i in range(0, h):
  wl.append([int(i) for i in input().split()])
 
 
n = {1:0}
 
while len(n) < 10:
  c = 1000
  mn = 10
  for a in n.keys():
    a2 = int(a)
    for b in range(0, 10):
      if not b in n:
        if k[b][a2] + n[a] < c:
          c = k[b][a2] + n[a]
          mn = b
  n[mn] = c
 
ans = 0
for a in range(0, h):
  for b in range(0, w):
    if wl[a][b] != -1:
      ans += n[wl[a][b]]
 
print(ans)
      

### FIXED CODE ###

h, w = [int(i) for i in input().split()]
k = []
wl = []
  
for i in range(0, 10):
  k.append([int(i) for i in input().split()])
for i in range(0, h):
  wl.append([int(i) for i in input().split()])
 
 
n = {1:0}
 
while len(n) < 10:
  c = 1000
  mn = 10
  for a in n.keys():
    a2 = int(a)
    for b in range(0, 10):
      if not b in n:
        if k[b][a2] + n[a] <= c:
          c = k[b][a2] + n[a]
          mn = b
  n[mn] = c
 
ans = 0
for a in range(0, h):
  for b in range(0, w):
    if wl[a][b] != -1:
      ans += n[wl[a][b]]
 
print(ans)
from itertools import product, combinations

INF = float('inf')
def floyd_warshall(E):
    N = len(E)
    dist = [[INF for _ in range(N)] for _ in range(N)]
    for v in V:
        dist[v][v] = 0
        for u, c in E[v]: dist[v][u] = c
    for k in V:        
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

N, M, L = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1].append((b-1, c))
    E[b-1].append((a-1, c))
dist = floyd_warshall(E)

E_charge = [[] for _ in V]
for u, v in combinations(V, 2):
    if dist[u][v] <= L:
        E_charge[u].append((v, 1))
        E_charge[v].append((u, 1))
charge = floyd_warshall(E_charge)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    n = charge[s-1][t-1]
    print(n - 1 if n != INF else -1)

### FIXED CODE ###

from itertools import product, combinations

INF = float('inf')
def floyd_warshall(E):
    N = len(E)
    dist = [[INF for _ in range(N)] for _ in range(N)]
    for v in range(N):
        dist[v][v] = 0
        for u, c in E[v]: dist[v][u] = c
    for k in range(N):        
        for i, j in product(range(N), repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

N, M, L = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1].append((b-1, c))
    E[b-1].append((a-1, c))
dist = floyd_warshall(E)

E_charge = [[] for _ in range(N)]
for u, v in combinations(range(N), 2):
    if dist[u][v] <= L:
        E_charge[u].append((v, 1))
        E_charge[v].append((u, 1))
charge = floyd_warshall(E_charge)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    n = charge[s-1][t-1]
    print(n - 1 if n != INF else -1)
r, d, x = map(int, input().split())
for i in range(10):
  x = r*x-D
  print(x)

### FIXED CODE ###

r, D, x = list(map(int, input().split()))
for i in range(10):
  x = r*x-D
  print(x)
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    A=LI()
    
    ng=-1
    ok=10**9
    
    def f(x):
        temp=0
        for i in range(N):
            temp+=(A[i]-0.1)//x
        
        return temp<=K
    
    while ok-ng>1:
        med=(ok+ng)//2
        if f(med):
            ok=med
        else:
            ng=med
               
    print(ok)
    

main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    A=LI()
    
    ng=0
    ok=10**9
    
    def f(x):
        temp=0#切る回数
        for i in range(N):
            temp+=(A[i]-0.1)//x
        
        return temp<=K
    
    while ok-ng>1:
        med=(ok+ng)//2
        if f(med):
            ok=med
        else:
            ng=med
               
    print(ok)
    

main()