Harryxun/stf_run huggingface dataset:
N, K = list(map(int, input().split()))


def check(k, hs, mx, mn, r):
    if mx - mn > r:
        return r
    if k == 0:
        return min(r, mx - mn)
    for i, h in enumerate(hs):
        hs.remove(h)
        r = min(r, check(k - 1, hs, max(mx, h), min(mn, h), r))
        hs.insert(i, h)
    return r


def main():
    hs = [int(input()) for i in range(N)]
    print(check(K, hs, 0, 10 ** 9, 10 ** 9))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, K = list(map(int, input().split()))
    hs = [int(input()) for i in range(N)]
    hs.sort()
    i = 0
    r = 10 ** 9
    while True:
        if i + K > N:
            break
        r = min(r, hs[i + K - 1] - hs[i])
        i += 1
    print(r)


if __name__ == '__main__':
    main()
a=input()
b=input()
if a<=b:
  s=b
  b=-1+b
else:
  s=a
  a=-1+a
if a<=b:
  t=b
else:
  t=a
print(s+t)

### FIXED CODE ###

a,b=map(int,input().split())
if a<=b:
  s=b
  b=-1+b
else:
  s=a
  a=-1+a
if a<=b:
  t=b
else:
  t=a
print(s+t)
N,K = map(int,input().split())
nums = list(map(int,input().split()))
nums.sort()
dif = []
cnt=[]
for i in range(N-1):
  if nums[i] != nums[i+1]:
    dif.append(i+1) #玉の番号の変わり目を記録する
for i in range(len(dif)+1):
  if i == 0:
    cnt.append(dif[0])
  if i == len(dif):
    cnt.append(N-dif[-1])
    break
  cnt.append(dif[i]-dif[i-1])
cnt.sort(reverse=True)#それぞれの球が何個ずつあるかのリスト作成
n = 0
if len(cnt)<=K:
  print(0)
else:
  for i in range(K):
    n+=cnt[i]
  print(N-n)
  
    
  


### FIXED CODE ###

N,K = map(int,input().split())
nums = list(map(int,input().split()))
nums.sort()
dif = []
cnt=[]
for i in range(N-1):
  if nums[i] != nums[i+1]:
    dif.append(i+1) #玉の番号の変わり目を記録する
if len(dif)==0:
  print(0)
else:
  for i in range(len(dif)+1):
    if i == 0:
      cnt.append(dif[0])
    if i == len(dif):
      cnt.append(N-dif[-1])
      break
    cnt.append(dif[i]-dif[i-1])
  cnt.sort(reverse=True)#それぞれの球が何個ずつあるかのリスト作成
  n = 0
  if len(cnt)<=K:
    print(0)
  else:
    for i in range(K):
      n+=cnt[i]
    print(N-n)
import numpy as np

N,M = [int(i) for i in input().split(" ")]
H = [int(i) for i in input().split(" ")]
mh = np.zeros([N])
for i in range(M):
    a,b = [int(i)-1 for i in input().split(" ")]
    mh[a] = max(mh[a],h[b])
    mh[b] = max(mh[b],h[a])

ans = 0
for i in range(N):
    if mh[i] < h[i]:
        ans += 1

print(ans)

### FIXED CODE ###

import numpy as np

N,M = [int(i) for i in input().split(" ")]
H = [int(i) for i in input().split(" ")]
mh = np.zeros([N])
for i in range(M):
    a,b = [int(i)-1 for i in input().split(" ")]
    mh[a] = max(mh[a],H[b])
    mh[b] = max(mh[b],H[a])

ans = 0
for i in range(N):
    if mh[i] < H[i]:
        ans += 1

print(ans)
N = [int(i) for i in input().split()] 

flag = ["","",""]

for i in range(1 << len(N)-1):
	print("i:", i)
	result = N[0]
	for j in range(len(N)-1):
		print("j:", j)
		if ((i >> j) & 1) == 1:
			result += N[j+1]
			flag[j] = "+"
		else:
			result -= N[j+1]
			flag[j] = "-"

	print("result:", result)

	if result == 7:
		break

print("%d%s%d%s%d%s%d=7" %(N[0],flag[0],N[1],flag[1],N[2],flag[2],N[3]))

### FIXED CODE ###

N = [int(i) for i in input()] 

flag = ["","",""]

for i in range(1 << len(N)-1):
	result = N[0]
	for j in range(len(N)-1):
		if ((i >> j) & 1) == 1:
			result += N[j+1]
			flag[j] = "+"
		else:
			result -= N[j+1]
			flag[j] = "-"

	if result == 7:
		break

print("%d%s%d%s%d%s%d=7" %(N[0],flag[0],N[1],flag[1],N[2],flag[2],N[3]))
import sys

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

for j in range(N+1):
    for k in range(N+1):
        if N-j-k<0:
            continue
        Total=10**4*(N-j-k)+5000*j+10**3*k
        if Total==Y:
        print("{} {} {}".format(N-j-k,j,k))
        sys.exit()
        
print("-1 -1 -1")

### FIXED CODE ###

import sys

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

for j in range(N+1):
    for k in range(N+1):
        if N-j-k<0:
            continue
        Total=10**4*(N-j-k)+5000*j+10**3*k
        if Total==Y:
            print("{} {} {}".format(N-j-k,j,k))
            sys.exit()
        
print("-1 -1 -1")
s = input()
if (s[:4] == 2019 and s[5] == 0 and s[6] <= 4) or (s[:4] < 2019):
    print("Heisei")
else:
    print("TBD")

### FIXED CODE ###

s = input()
 
if s <= '2019/04/30':
    print('Heisei')
else:
    print('TBD')
n = int(input())
s = list(input())
 
a = 0
 
for i in range(n):
  if s[i]=='R':
    for j in range(n):
      if s[j]=='G':
        for k in range(n):
          if s[k]=='B':
            if i<j<k:
              if (j-i)!=(k-j):
                a = a + 1
            elif j<k<i:
              if (k-j)!=(i-k):
                a = a + 1
            elif k<i<j:
              if abs(j-i)!=abs(k-i):
                a = a + 1
            elif j<i<k:
              if abs(j-i)!=abs(k-i):
                a = a + 1
            elif i<k<j:
              if abs(k-i)!=abs(k-j):
                a = a + 1
            elif k<j<i:
              if abs(j-i)!=abs(k-j):
                a = a + 1
          
print(a)
n = int(input())
s = list(input())

a = 0

for i in range(n):
  if s[i]=='R':
    for j in range(n):
      if s[j]=='G':
        for k in range(n):
          if s[k]=='B':
            if i<j<k:
              if (j-i)!=(k-j):
                a = a + 1
            elif i<k<j:
              if (k-i)!=(j-k):
                a = a + 1
            elif j<i<k:
              if (i-j)!=(k-i):
                a = a + 1
            elif j<k<i:
              if (k-j)!=(i-k):
                a = a + 1
            elif k<i<j:
              if (i-k)!=(j-i):
                a = a + 1
            elif k<j<i:
              if (j-k)!=(i-j):
                a = a + 1
          
print(a)

### FIXED CODE ###

n = int(input())
s = input()
 
count = {"R":0,"G":0,"B":0}
for c in s:
    count[c] += 1
 
r,g,b = count.values()
ans = r*g*b
for i in range(1,(n-1)//2+1): #1から
    for rgb in zip(s,s[i:],s[i*2:]):  #rgbに連続した三つのリストの要素を入れ込む
        if len(set(rgb)) == 3:  #リストrgbをセットにまとめ、長さが
            ans -=1
print(ans)
from itertools import *
def f(s):
 for t in[f"({a} {x} {b}) {y} ({c} {z} {d})",f"(({a} {x} {b}) {y} {c}) {z} {d}",f"{a} {x} ({b} {y} ({c} {z} {d}))",f"({a} {x} ({b} {y} {c})) {z} {d}",f"{a} {x} (({b} {y} {c}) {z} {d})"]:
  for a,b,c,d in permutations(s):
   for x,y,z in product('+-*',repeat=3):
    if eval(t)==10:return'('+t+')'
 else:return 0
for e in iter(input,'0 0 0 0'):print(f(list(map(int,e.split()))))


### FIXED CODE ###

from itertools import *
g=lambda a,x,b:{'+':a+b,'-':a-b,'*':a*b}[x]
def f(s):
 for a,b,c,d in permutations(s):
  for x,y,z in product('+-*',repeat=3):
   if g(g(g(a,x,b),y,c),z,d)==10:return f"(({a}{x}{b}){y}{c}){z}{d}"
   if g(g(a,x,b),y,g(c,z,d))==10:return f"({a}{x}{b}){y}({c}{z}{d})"
 return 0
for e in iter(input,'0 0 0 0'):print(f(list(map(int,e.split()))))
#coding:utf-8
import numpy as np

n = int(input())
inf = 1000000000000000

def minHeapify(Q,i):
    H = len(Q)
    l = 2*i
    r = 2*i + 1
    if l < H and Q[l][1] < Q[i][1]:
        smallest = l
    else:
        smallest = i
    if r < H and Q[r][1] < Q[smallest][1]:
        smallest = r

    if smallest != i:
        Q[i], Q[smallest] = Q[smallest], Q[i]
        minHeapify(Q,smallest)

def buildMinHeap(Q):
    H = len(Q)
    for i in range(H // 2, -1, -1):
        minHeapify(Q,i)

def Insert(Q,key):
    v = key[0]
    Q.append([v,inf])
    lens = len(Q)
    heapIncreaseKey(Q,lens-1,key)

def heapIncreaseKey(Q,i,key):
    Q[i][1] = key[1]
    while i > 0 and Q[i // 2][1] > Q[i][1]:
        Q[i], Q[i // 2] = Q[i // 2], Q[i]
        i //= 2

def heapExtractMin(Q):
    H = len(Q)
    minv = Q[0][0]
    Q[0] = Q[H-1]
    Q.pop()
    minHeapify(Q,0)
    return minv




def dijkstra(s):
    color = ["white" for i in range(n)]
    d = [inf for i in range(n)]
    d[s] = 0
    Q = [[s,0]]
    while Q != []:
        u = heapExtractMin(Q)
        color[u] = "black"
        for vw in mtrx[u]:
            [v,w] = vw
            if color[v] != "black":
                if d[u] + w < d[v]:
                    d[v] = d[u] + w
                    color[v] = "gray"
                    Insert(Q,[v,d[v]])
    return d



mtrx = [[] for i in range(n)]
for i in range(n):
    col = list(map(int,input().split()))
    u,k = col[0], col[1]
    for j in range(k):
        [v,w] = col[2*j+2: 2*j+4]
        mtrx[u].append([v,w])



d = dijkstra(0)
for i,j in enumerate(d):
    print(i,j)


### FIXED CODE ###

#coding:utf-8
n = int(input())
inf = 1000000000000000

def minHeapify(Q,i):
    H = len(Q)
    l = 2*i
    r = 2*i + 1
    if l < H and Q[l][1] < Q[i][1]:
        smallest = l
    else:
        smallest = i
    if r < H and Q[r][1] < Q[smallest][1]:
        smallest = r

    if smallest != i:
        Q[i], Q[smallest] = Q[smallest], Q[i]
        minHeapify(Q,smallest)

def buildMinHeap(Q):
    H = len(Q)
    for i in range(H // 2, -1, -1):
        minHeapify(Q,i)

def Insert(Q,key):
    v = key[0]
    Q.append([v,inf])
    lens = len(Q)
    heapIncreaseKey(Q,lens-1,key)

def heapIncreaseKey(Q,i,key):
    Q[i][1] = key[1]
    while i > 0 and Q[i // 2][1] > Q[i][1]:
        Q[i], Q[i // 2] = Q[i // 2], Q[i]
        i //= 2

def heapExtractMin(Q):
    H = len(Q)
    minv = Q[0][0]
    Q[0] = Q[H-1]
    Q.pop()
    minHeapify(Q,0)
    return minv




def dijkstra(s):
    color = ["white" for i in range(n)]
    d = [inf for i in range(n)]
    d[s] = 0
    Q = [[s,0]]
    while Q != []:
        u = heapExtractMin(Q)
        color[u] = "black"
        for vw in mtrx[u]:
            [v,w] = vw
            if color[v] != "black":
                if d[u] + w < d[v]:
                    d[v] = d[u] + w
                    color[v] = "gray"
                    Insert(Q,[v,d[v]])
    return d



mtrx = [[] for i in range(n)]
for i in range(n):
    col = list(map(int,input().split()))
    u,k = col[0], col[1]
    for j in range(k):
        [v,w] = col[2*j+2: 2*j+4]
        mtrx[u].append([v,w])



d = dijkstra(0)
for i,j in enumerate(d):
    print(i,j)
A,B,N = map(int,input().split())

if N<= B-1:
    ans = (N*A)//B
else:
    ((B-1)*A)//B
    
print(ans)

### FIXED CODE ###

A,B,N = map(int,input().split())

if N<= B-1:
    ans = (N*A)//B
else:
    ans = ((B-1)*A)//B
    
print(ans)
n = int(input())

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

a = 0

for i in range(len(l)):
    for j in range(i+1,len(l)):
        a = a + int(len([for k in l if i > l[i]+l[j]]))
        

print(a)

### FIXED CODE ###

import bisect
n = int(input())
 
l = list(map(int, input().split()))
l.sort()
a = 0
#print(l)
for i in range(n-2):
    for j in range(i+1,n-1):
        s = bisect.bisect_left(l,l[i]+l[j])-j-1
        a+=s


print(a)
n = int(input())
s = input()
mx = 0
for i in range(N-1):
  a = [ord(aa) for aa in s[:i+1]]
  b = [ord(bb) for bb in s[i+1:]]
  counter = 0
  for c in range(ord('a'), ord('z')):
    if c in a and c in b:
      counter += 1
  if mx < counter:
    mx = counter

print(counter)
    
    

### FIXED CODE ###

n = int(input())
s = input()
mx = 0
for i in range(n-1):
  a = [ord(aa) for aa in s[:i+1]]
  b = [ord(bb) for bb in s[i+1:]]
  counter = 0
  for c in range(ord('a'), ord('z')+1):
    if (c in a) and (c in b):
      counter += 1
  if mx < counter:
    mx = counter

print(mx)
def f(n, l):
  sum = 0
  for i in range(1, n+1):
    sum += i
    if sum >= n:
      return i

print(f(n, l))

### FIXED CODE ###

n = int(input())
l = []

def f(n, l):
  sum = 0
  for i in range(1, n+1):
    sum += i
    if sum >= n:
      return i

print(f(n, l))
from scipy.special import comb
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()
res = 0
MOD = 10**9+7
nCk_2 = dict()
for k in range(K-2,N):
    nCk_2[k] = int(comb(k, K-2))%MOD
for i in range(N):
    for j in range(N):
        if N-i-j >= K:
            res += int((A[N-1-j]-A[i])*nCk_2[N-j-2-i]%MOD)
        if N-1-j < i:
            break
print(res)


### FIXED CODE ###

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()
res = 0
MOD = 10**9+7
nCk_2 = dict()
fac, finv, inv = [0]*(N+1), [0]*(N+1), [0]*(N+1)
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,N+1):
    fac[i] = fac[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD
def comb(n, k):
    return (fac[n]*((finv[k]*finv[n-k])%MOD))%MOD
s = [1,-1]
for m in range(2):
    for i in range(K-1,N):
        res = (res + s[m]*int((A[i])*comb(i,K-1)))%MOD
    A = sorted(A, reverse=True)
print(res)
import fractions

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

mod = 10**9+7

R = 1 # 最小公倍数
# 最小公倍数を求める
for A in A_list:
    R *= A // fractions.gcd(R, A)

# Bの合計を求める
ans = 0
for A in A_list:
    ans = ans + (R / A)

print(int(ans%(mod+7)))


### FIXED CODE ###

import fractions

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

mod = 10**9+7

R = 1 # 最小公倍数
# 最小公倍数を求める
for A in A_list:
    R *= A // fractions.gcd(R, A)

# Bの合計を求める
ans = 0
for A in A_list:
    ans = ans + R // A # 計算は小数として出してはダメだから//を使う

ans %= mod

print(ans)
def comb(n, r):
  if r == 0  or n == r: return 1
  else: return comb(n-1, r) + comb(n-1, r-1)
 
k, s = map(int, input().split())
print(comb(s-3k+2, 2))

### FIXED CODE ###

ans = 0
k, s = map(int, input().split())
for x in range(k+1):
  for y in range(k+1):
    z = s - x - y
    if 0 <= z and z <= k:
      ans += 1
 
 
 
print(ans)
a,b,c,d=map(int,open(0).readlines());print([a,b][a>b]+[c,d][c>d])

### FIXED CODE ###

print(input()[0]+input()[1]+input()[2])
N,K = map(int, input().split())
V = list(map(int, input().split()))

ans = 0
nums = min(N, K)
for i in range(nums): # 左端から取り出す回数
    for j in range(nums-i): # 右端から取り出す回数
        for k in range(nums-i-j): # Dに戻す個数
            L = V[:i]
            R = V[N-j:]
            if L == []: L = [0]
            if R == []: R = [0]
            LR = L + R
            LR.sort()
            cnt = 0
            while cnt <= k:
                if LR[cnt] < 0:
                    cnt += 1
                else:
                    break
            ans = max(ans, sum(LR[cnt:]))

print(ans)

### FIXED CODE ###

N,K = map(int, input().split())
V = list(map(int, input().split()))

ans = 0

for i in range(N+1): # 左端から取り出す回数
    for j in range(N+1-i): # 右端から取り出す回数
        L = V[:i]
        if j == 0:
            R = []
        else:
            R = V[-j:]
        LR = L + R
        if len(LR) > K:
            continue
        num_drop = min(len(LR), K-i-j)
        LR.sort()
        total = sum(LR)
        idx = 0
        while idx < num_drop:
            if LR[idx] < 0:
                total -= LR[idx]
                idx += 1
            else:
                break
        ans = max(ans, total)


print(ans)
import sys
sys.setrecursionlimit(10000000)
n,k=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
MOD=10**9+7
def coloring(node,pre):
  if len(graph[node])>k:
    return 0
  if pre==-1:
    color=k-1
  else:
    color=k-2
  ans=1
  for i in graph[node]:
    if i==pre:continue
    ans*=color
    ans%=MOD
    color-=1
  for i in graph[node]:
    if i==pre:continue
    ans*=coloring(i,node)
    ans%=MOD
  return ans
print((k*coloring(0,-1))%MOD)


### FIXED CODE ###

n,a,b=map(int,input().split())
print(min(b,n*a))
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)

    if temp!=1:
        arr.append(temp)

    return arr

N=int(input())
A=list(map(int, input().split()))
p=1
A=sorted(A)
num1=A.count(1)
B=list(set(A))
if len(B)<len(A)-num1+1:
    p=0
S=set(factorization(B[0]))
T=set(factorization(B[0]))
flg=0
for i in range(1,len(B)):
    prime=set(factorization(B[i])
    if T&prime!=set():
        flg=1
    S=S&prime
    T=T|prime    #print(S,T)
if S!=1:
    print('not coprime')
elif flg==1 or p=0:
    print('setwise coprime')
else:
    print('pairwise coprime')


### FIXED CODE ###

from math import gcd
from functools import reduce

def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(4, n + 1, 2):
        sieve[i] = 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i * 2):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):#1を除く(素因数,指数)のリスト
    result = []
    while n != 1:
        p = prime_table[n]
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        result.append((p, e)) 
    return result


def f():
    s = set()
    for i in range(N):
        t = prime_factorize(A[i])
        for p, _ in t:
            if p in s:
                return False
            s.add(p)
    return True


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

prime_table = make_prime_table(10 ** 6)
if f():
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')
a,b,c = map(int, input().split())

print [for i in range(a,b+1):
    if c % i == 0

### FIXED CODE ###

a,b,c = map(int,input().split())
count = 0
for i in range(a,b+1):
    d = c % i
    if d == 0:
        count += 1
print (count)
a = list(input())
b = list(input())
c = list(input())
# print('a',a)
# print('b',b)
# print('c',c)
# exit()
ptr = 'a'
while (True):
	if ptr == 'a':
		ptr = a.pop(0)
	if ptr == 'b':
		ptr = b.pop(0)
	if ptr == 'c':
		ptr = c.pop(0)

	if ptr == 'a' and a == []:
		print('A')
		break
	elif ptr == 'b' and  b == []:
		print('B')
		break
	elif ptr == 'c' and c == []:
		print('C')
		break

### FIXED CODE ###

a = list(input())
b = list(input())
c = list(input())
# print('a',a)
# print('b',b)
# print('c',c)
# exit()
ptr = 'a'
while (True):
	if ptr == 'a':
		if a == []:
			print('A')
			break
		ptr = a.pop(0)
	if ptr == 'b':
		if b == []:
			print('B')
			break
		ptr = b.pop(0)
	if ptr == 'c':
		if c == []:
			print('C')
			break
		ptr = c.pop(0)
from itertools import combinations
import numpy as np

n,m,x = map(int, input().split())
q = [np.array(list(map(int, input().split()))) for _ in range(n)]
L=[]
for i in range(1,n):
    for j in list(combinations(q,i)):
        S = np.sum(j, axis=0)
        if all([k >= x for k in S[1:]]):
            L.append(S[0])

if len(L) >0:
    print(min(L))
else:
    print(-1)


### FIXED CODE ###

from itertools import combinations
import numpy as np

n,m,x = map(int, input().split())
q = [np.array(list(map(int, input().split()))) for _ in range(n)]
L=[]
for i in range(1,n+1):
    for j in list(combinations(q,i)):
        S = np.sum(j, axis=0)
        if all([k >= x for k in S[1:]]):
            L.append(S[0])

if len(L) >0:
    print(min(L))
else:
    print(-1)
n, m = map(int, input().split())
a = sorted([int(x) for x in  input().split()])
for _ in range(m):
    b, c = map(int, input().split())
    if a[0] < c:
        for i in range(b):
            if a[i] < c:
                a[i] = c
        a.sort()
print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())

gate_cond = [[int(x) for x in input().split()] for _ in range(m)]
max_under_th = max([l[0] for l in gate_cond])
min_upper_th = min([l[1] for l in gate_cond])
if min_upper_th - max_under_th >= 0:
    print(min_upper_th - max_under_th + 1)
else:
    print(0)
from heapq import heappush, heappop
INF = 10 ** 20

while True:
  n, m, l, k, a, h = map(int, input().split())
  if n == 0:
    break
  if l != 0:
    sisetu = list(map(int, input().split())) + [a, h]
  else:
    sisetu = [a, h]

  costs = [[INF] * n for _ in range(n)]
  for _  in range(k):
    x, y, t = map(int, input().split())
    costs[x][y] = t
    costs[y][x] = t
  for i in range(n):
    costs[i][i] = 0
  for k in range(n):
    for j in range(n):
      for i in range(n):
        costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j])

  edges = [[] for _ in range(n)]
  for i in range(n):
    for j in range(n):
      if i != j and i in sisetu and j in sisetu and costs[i][j] <= m:
        edges[i].append((costs[i][j], j))

  que = []
  heappush(que, (0, a))
  cost = [INF] * n
  cost[0] = 0
  while que:
    total, node = heappop(que)
    for dist, to in edges[node]:
      if total + dist < cost[to]:
        cost[to] = total + dist
        heappush(que, (total + dist, to))
  if cost[h] == INF:
    print("Help!")
  else:
    print(cost[h] + (cost[h] - m))


### FIXED CODE ###

from heapq import heappop, heappush
INF = 10 ** 20

def main():
  while True:
    n, m, l, k, a, h = map(int, input().split())
    if n == 0:
      break
  
    if l == 0:
      input()
      sisetu = [a, h]
    else:
      sisetu = list(map(int, input().split()))
      sisetu += [a, h]
  
    edges = [[] for _ in range((m + 1) * n)]
    for _ in range(k):
      x, y, t = map(int, input().split())
      for i in range(t, m + 1):
        edges[i * n + x].append((t, (i - t) * n + y))
        edges[i * n + y].append((t, (i - t) * n + x))
    
    for node in sisetu:
      for i in range(m):
        edges[i * n + node].append((1, (i + 1) * n + node))
  
    que = []
    heappush(que, (0, m * n + a))
    costs = [INF] * ((m + 1) * n)
    costs[m * n + a] = 0
    
    while que:
      total, node = heappop(que)
      for dist, to in edges[node]:
        if costs[to] > total + dist:
          costs[to] = total + dist
          heappush(que, (total + dist, to))
    ans = min([costs[i * n + h] for i in range(m + 1)])
    if ans == INF:
      print("Help!")
    else:
      print(ans)

main()
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    BC = []

    D = []
    for i in range(M):
        b, c = map(int, input().split())
        BC.append((b, c))
    BC.sort(key=lambda x: x[1], reverse=True)
    ld = 0
    for b, c in BC:
        D += [c] * b
        ld += b
        if ld > N:
            break
    
    res = 0
    A.sort()
    for i in range(N):
        res += max(A[i], D[i])
        

    res = 0
    for i in range(N):
        res += max(A[i], D[i])

    print(res)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    BC = []

    D = []
    for i in range(M):
        b, c = map(int, input().split())
        BC.append((b, c))
    BC.sort(key=lambda x: x[1], reverse=True)
    ld = 0
    for b, c in BC:
        D += [c] * b
        ld += b
        if ld > N:
            break
    
    res = 0
    A.sort()
    for i in range(N):
        if i < ld:
            res += max(A[i], D[i])
        else:
            res += A[i]
    

    print(res)

if __name__ == "__main__":
    main()
a = (int,input())
print(a + a^2 + a^3)


### FIXED CODE ###

a = input()
b = int(a)
print(b+b**2+b**3)
N ,M=map(float,input().split())
print(int((1900*M+100*(N-M)*2**M))


### FIXED CODE ###

N ,M=map(float,input().split())
print(int((1900*M+100*(N-M))*2**M))