Harryxun/stf_run huggingface dataset:
def main() -> None:
    ab, bc, ca = map(int, input())
    print(ab * bc // 2)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main() -> None:
    ab, bc, ca = map(int, input().split())
    print(ab * bc // 2)


if __name__ == "__main__":
    main()
import sys
input = sys.stdin.readline
import numpy as np

n,m = (int(x) for x in input().split())
a = list(map(int, input().split()))

b = np.zeros(m)
idx = 0

for i in range(n):
	for j in range(n):
		if b[idx] < a[i]+a[j]:
			b[idx] = a[i]+a[j]
			idx = np.argmin(b)

print(int(sum(b)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
# 昇順ソートされた配列の挿入位置indexを返す O(logN)
from bisect import bisect_left

def isOver(a,n,x):
	cnt = 0
	for i in range(n):
		cnt += n-bisect_left(a,x-a[i])
	return cnt

def calX(a,n,m,l,r):
	while r-l>1:
		# x: 握手で得たい最低パワー値
		x = (l+r)//2
		if isOver(a,n,x) >= m:
			l = x
		else: #握手する限界回数すら満たせないほど大きいxなら
			r = x 
	return l

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

#累積和の下準備
a.sort()
s = [0]*(n+1)
for i in range(n):
	s[i+1] = s[i]+a[i]

x = calX(a,n,m,a[0]*2,a[n-1]*2)

out = 0
for i in range(n):
	idx = bisect_left(a,x-a[i])
	out += s[n]-s[idx]+a[i]*(n-idx)

out -= (isOver(a,n,x)-m)*x

print(out)
def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
a,b=n1()
from math import gcd
m=gcd(a,b)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

def primes(n):
    num = [True]*n
    num[0] = num[1] = False
    for i in range(2,int(n**0.5)+1):
        if num[i]:
            for j in range(i**2, n, i):
                num[j] = False
    return [i for i in range(2,n) if num[i]]

gcd_list=make_divisors(m)
if len(gcd_list)==1:
    print(1)
else:
    prime_list=primes(gcd_list[-1])
    ans=1
    for i in gcd_list[1:]:
        if i in prime_list:
            ans+=1
    print(ans)

### FIXED CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
a,b=n1()
# from math import gcd
from fractions import gcd
m=gcd(a,b)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

gcd_list=make_divisors(m)
if len(gcd_list)==1:
    print(1)
else:
    prime=[]
    for i in gcd_list[1:]:
        for j in prime:
            if i%j==0:
                break
        else:
            prime.append(i)
    print(len(prime)+1)
def f(n):
    a=0
    while n%2==0:
        n//=2
        a+=1
    return a    
n,m,*a=map(int,open(0).read().split())
c=[f(i) for i in a]
if sum(c)!=c[0]*n:
    print(0)
    exit()
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
a=list(set(a))
b=a[0]*a[1]// fractions.gcd(a[0], a[1])
for i in a:
    b=lcm(i,b)
print(0 if b//2>m else (m-b//2)//b+1)  

### FIXED CODE ###

def f(n):
    a=0
    while n%2==0:
        n//=2
        a+=1
    return a    
n,m,*a=map(int,open(0).read().split())
c=[f(i) for i in a]
if sum(c)!=c[0]*n:
    print(0)
    exit()
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
a=list(set(a))
a=[i//(2**c[0]) for i in a]
b=a[0]
for i in a:
    b=lcm(i,b)
    if b*(2**c[0])>2*m:
        print(0)
        exit()
b*=2**c[0]    
print(0 if b//2>m else (m-b//2)//b+1)
s = list(input())
t = list(input())
s.sort()
t.sort(reverse=True)
for i in range(100):
    if bool(s[i:i+1]) == False:
        if t[i:i+1]:
            print("Yes")
            break
        else:
            print("No")
            break
    elif bool(t[i:i+1]) == False:
        print("No")
        break
    elif (s[i] < t[i]):
        print("Yes")
        break
    elif (s[i] > t[i]):
        print("No")
        break

### FIXED CODE ###

a,b = map(int, input().split())
c = -(-(a + b)//2)
print("{}".format(c))
import numpy as np
import sys
from numba import njit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def make_divisors(n):
    divisors = np.zeros(0,np.int32)
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors = np.append(divisors,i)
            if i != n // i:
                divisors = np.append(divisors,n//i)
    return divisors

@njit
def ok(i,a):
  def make_divisors(n):
    divisors = np.zeros(0,np.int32)
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors = np.append(divisors,i)
            if i != n // i:
                divisors = np.append(divisors,n//i)
    return divisors
    x = a[i]
    for j in make_divisors(x):
        for k in range(n):
            if i != k and j == a[k]:
                break
        else:
            continue
        break
    else:
        return 1
    return 0

n = int(readline())
a = list(map(int,input().split()))
a = np.array(a,np.int32)
ans = 0
for i in range(n):
    ans += ok(i,a)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
ok = [1]*(10**6+1)
ans = 0
for i in range(n):
    if ok[a[i]]:
        if i < n-1:
            if a[i+1] != a[i]:
                ans += 1
        else:
            ans += 1
        for j in range(1,10**6//a[i]+1):
            ok[a[i]*j] = 0
print(ans)
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = list(int())
if "9" in N:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = list(input())
if "9" in N:
    print("Yes")
else:
    print("No")
n,a,b = map(int,input().split())

#制限なしで全ての花束の作り方
wa = pow(2, n, 10 ** 9 + 7) - 1

#a本の花束の作り方
#val1 = comb(n, a, exact=True)
#val2 = comb(n, b, exact = True)

x = 1
y = 1
for i in range(a):
    x = (x * (n-i)) % (10 ** 9 + 7)
    y = (y * (i+1)) % (10 ** 9 + 7)
val1 = (x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7)) % (10 ** 9 + 7)

x = 1
y = 1
for i in range(b):
    x = (x * (n-i)) % (10 ** 9 + 7)
    y = (y * (i+1)) % (10 ** 9 + 7)

val2 = (x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7)) % (10 ** 9 + 7)

ans = wa - val1 - val2
for i in range(100):
if ans < 0:
    ans += 10 ** 9 + 7
print(ans)

### FIXED CODE ###

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

#制限なしで全ての花束の作り方
wa = pow(2, n, 10 ** 9 + 7) - 1

#a本の花束の作り方
#val1 = comb(n, a, exact=True)
#val2 = comb(n, b, exact = True)

x = 1
y = 1
for i in range(a):
    x = (x * (n-i)) % (10 ** 9 + 7)
    y = (y * (i+1)) % (10 ** 9 + 7)
val1 = (x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7)) % (10 ** 9 + 7)

x = 1
y = 1
for i in range(b):
    x = (x * (n-i)) % (10 ** 9 + 7)
    y = (y * (i+1)) % (10 ** 9 + 7)

val2 = (x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7)) % (10 ** 9 + 7)

ans = wa - val1 - val2
for i in range(100):
    if ans < 0:
        ans += 10 ** 9 + 7
print(ans)
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(float, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(1e9)
mod=int(1e9)+7


n=int(data())
P=list(mdata())
dp=[0]*(n//2+2)
dp[1]=1
for i in range(n):
    dp1=dp.copy()
    for j in range(1,len(dp)):
        k=dp[j-1]*(1-P[i])+dp[j]*(P[i])
        dp1[j]=k
    dp=dp1.copy()
print(sum(dp))




### FIXED CODE ###

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(float, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(1e9)
mod=int(1e9)+7


n=int(data())
P=list(mdata())
dp=[0]*(n//2+2)
dp[1]=1
for i in range(n):
    dp1=dp[:]
    for j in range(1,len(dp)):
        k=dp[j-1]*(1-P[i])+dp[j]*(P[i])
        dp1[j]=k
    dp=dp1[:]
print(sum(dp))
import math
n, x, t = map(int, input().split())

print(t * math(n/x))

### FIXED CODE ###

import math
n, x, t = map(int, input().split())
 
print(t * math.ceil(n/x))
def main():
    N = int(input())

    xn = []
    yn = []
    hn = []

    for i in range(N):
        xi, yi, hi = map(int, input().split())
        if hi:
            xn.append(xi)
            yn.append(yi)
            hn.append(hi)

    if N == 1:
        print(xn[0], yn[0], hn[0])
        return

    for Cx in range(101):
        for Cy in range(101):

            last = None

            for i in range(N):
                H = abs(xn[i] - Cx) + abs(yn[i] - Cy) + hn[i]

                if H < 0:
                    continue
                if last:
                    if (last != H):
                        break

                last = H
            else:
                print(Cx, Cy, H)
                return


main()


### FIXED CODE ###

import sys

input = sys.stdin.readline

N = int(input())

xn = [0] * N
yn = [0] * N
hn = [0] * N

for i in range(N):
    xi, yi, hi = map(int, input().split())
    xn[i] = xi
    yn[i] = yi
    hn[i] = hi

div = 0

for Cx in range(101):
    for Cy in range(101):
        for i in range(N):

            if 0 < hn[i]:
                h = abs(xn[i] - Cx) + abs(yn[i] - Cy) + hn[i]
                if div in [0, 2]:
                    H = h
                    div = 1
                else:
                    if (H != h):
                        div = 2
                        break

        if div == 2:
            continue

        for i in range(N):
            if 0 == hn[i]:
                h = abs(xn[i] - Cx) + abs(yn[i] - Cy)
                if h < H:
                    div = 2
                    break

        if div == 2:
            continue

        print(Cx, Cy, H)
        break

    if div == 1:
        break
a=[0]*9;input()
for x in list(map(int,input().split())):
    if x<3200:a[x//400]=1
    else:a[x//400]+=1
b=sum(a[:8]);print(b,b*(b==8)or b+a[8])

### FIXED CODE ###

input();a=[0]*9
for x in input().split():
    x=int(x)
    if x>3599:x=3200
    a[x//400]+=1
b=sum([1 if x else 0 for x in a[:8]])
print(max(1,b),b+a[8])
n = int(input())
result = 0
for b in range(n):
  for p in range(n):
    if b**p => n and result < b**p:
      result = b**p
      break

print(int(result))

### FIXED CODE ###

n = int(input())
result = pow(int(n**(1/2)), 2)
for b in range(1, n):
  for p in range(2, n):
    if b**p > n:
        break
    elif b**p > result:
        result = b**p

print(int(result))
from scipy.special import comb

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

Min = 0
Max = 0

a_sort = sorted(a)
for i, num in enumerate(a_sort):
    if i >= k-1:
        Min += comb(i, k-1, exact=True) * num
    if n-i >= k:
        Max += comb(n-i-1, k-1, exact=True) * num

print(int((Min - Max) % (10e08+7)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
 
class Combination():
    # コンストラクタ
    def __init__(self, N:int, P:int):
        self.N = N
        self.P = P
 
        # fact[i] = (i! mod P)
        self.fact = [1, 1]   
        # factinv[i] = ((i!)^(-1) mod P)
        self.factinv = [1, 1]
        # factinv 計算用
        self.inv = [0, 1]    
 
        for i in range(2, N+1):
            self.fact.append((self.fact[-1] * i) % P)
            self.inv.append((-self.inv[P % i] * (P // i)) % P)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % P)
    
    # nCk (mod P)   (ただし、n<=N)
    def getComb(self, n:int, k:int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] * self.factinv[n-k] % self.P
 
def main():
    N,K = map(int,input().split())
    A = sorted([int(i) for i in input().split()])
 
    mod = 10**9+7
 
    COMB = Combination(N,mod)
 
    cmb = [0] * (N-K+1)
    for i in range(N-K+1):
        cmb[i] = COMB.getComb(i+(K-1),K-1)
 
    sum_max = 0
    for i in range(K-1,N):
        sum_max = (sum_max + cmb[i-(K-1)] * A[i]) % mod
 
    sum_min = 0
    for i in range(N-K,-1,-1):
        sum_min = (sum_min + cmb[(N-K)-i] * A[i]) % mod
 
    answer = sum_max - sum_min
    print(answer % mod)
 
if __name__ == "__main__":
    main()
N, K = map(int, input().split())

probability = 0
X = 1
cnt = 0
while True:
    X *= 2
    cnt += 1
    if X >= K:
        break

for i in range(1, K+1):
    probability += 1/2**cnt
    cnt -= 1

print((probability + N - K) / N)

### FIXED CODE ###

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

P = 0
for i in range(1, N+1):
    if i < K:
        cnt = 0
        while True:
            i *= 2
            cnt += 1
            if i >= K:
                P += 1 / (2 ** cnt)
                break
    else:
        P += 1

print(P / N)
import sys
while 1:
    H,W = map(int,sys.stdin.readline().split())
    print(('#'*W + '\n')*H)

### FIXED CODE ###

import sys
while 1:
    H,W = map(int,sys.stdin.readline().split())
    if H == W == 0:
        break
    print(('#'*W + '\n')*H)
A , B, C, K = map(int, input().split())
result = 0
for i in range(K):
    if A > 0:
        result +=1
        A -= 1
    elif B > 0:
        B -= 1
    else:
        result -= 1
        c -= 1
print(result)

### FIXED CODE ###

A , B, C, K = map(int, input().split())

if K >= A:
    result = A
    K -= A
else:
    result = K
    K = 0

if K >= B:
    K -= B

if K > 0:
    result -=K
print(result)
A, B, K = map(int, input().split())
ab = [int(i) for i in range(A, B + 1)]
ba = sorted(ab, reverse=True)
ans = []

for i in range(K):
    ans.append(ab[i])
    ans.append(ba[i])

ans = sorted(set(ans))
for i in ans:
    print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())

if b-a+1 <= 2*k:
    for num in range(a, b+1):
        print(num)
else:
    for num in range(a, a+k):
        print(num)
    for num in range(b-k+1,b+1):
        print(num)
#-*- coding:utf-8 -*-
"""
高橋くんは今日も1人でしりとりの練習をしています。

しりとりとは以下のルールで遊ばれるゲームです。

・はじめ、好きな単語を発言する
・以降、次の条件を満たす単語を発言することを繰り返す
　・その単語はまだ発言していない単語である
　・その単語の先頭の文字は直前に発言した単語の末尾の文字と一致する

高橋くんは、10秒間にできるだけ多くの単語を発言する練習をしています。
高橋くんが発言した単語の個数Nとi番目に発言した単語Wiが与えられるので、
どの発言もしりとりのルールを守っていたかを判定してください。
"""
def check(words):
    answer = "Yes"
    for i in range(0, len(words)):
        for j in range(i, len(words)):
            if(words[i] == words[j]):
                answer = "No"

    return answer


def main(str):
    words = str.split()
    answer = check(words)
    print(answer)


if __name__ == "__main__":
    num = int(input())  # 単語の個数の読み込み
    str = [input() for i in range(0, num)]  # 単語の読み込み
    main(str)

### FIXED CODE ###

#-*- coding:utf-8 -*-
"""
高橋くんは今日も1人でしりとりの練習をしています。

しりとりとは以下のルールで遊ばれるゲームです。

・はじめ、好きな単語を発言する
・以降、次の条件を満たす単語を発言することを繰り返す
　・その単語はまだ発言していない単語である
　・その単語の先頭の文字は直前に発言した単語の末尾の文字と一致する

高橋くんは、10秒間にできるだけ多くの単語を発言する練習をしています。
高橋くんが発言した単語の個数Nとi番目に発言した単語Wiが与えられるので、
どの発言もしりとりのルールを守っていたかを判定してください。
"""
def check(words):
    answer = "Yes"

    # 同じ単語を使っていないか確認
    for i in range(0, len(words)):
        for j in range(i+1, len(words)):
            if(words[i] == words[j]):
                answer = "No"

    # 単語の最初と最後が一致しているか確認
    for i in range(0, len(words)-1):
        if(words[i][-1] != words[i+1][0]):
            answer = "No"

    return answer


def main(words):
    answer = check(words)
    print(answer)


if __name__ == "__main__":
    num = int(input())  # 単語の個数の読み込み
    str = [input() for i in range(0, num)]  # 単語の読み込み
    main(str)
n = map(int, input().split())

while n < 0:
    a += n
    n -= 1
print(a)


### FIXED CODE ###

n = int(input())
a = 0
while n > 0:
    a += n
    n -= 1
print(a)
import math

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

if n == 2:
    print(max(nums))
else:
    l_gcds = [nums[0]]
    r_gcds = [nums[-1]]
    for i in range(1, n):
        l = math.gcd(l_gcds[-1], nums[i])
        r = math.gcd(r_gcds[-1], nums[n - i - 1])
        l_gcds.append(l)
        r_gcds.append(r)
    r_gcds = r_gcds[::-1]
    gcds = [l_gcds[-2], r_gcds[1]]
    for i in range(1, n - 1):
        gcds.append(math.gcd(l_gcds[i - 1], r_gcds[i + 1]))
    print(max(gcds))

### FIXED CODE ###

def gcd(a, b):
    while True:
        a, b = b, a % b
        if b == 0:
            break
    return a


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

if n == 2:
    print(max(nums))
else:
    l_gcds = [nums[0]]
    r_gcds = [nums[-1]]
    for i in range(1, n - 1):
        l = gcd(l_gcds[-1], nums[i])
        r = gcd(r_gcds[-1], nums[n - i - 1])
        l_gcds.append(l)
        r_gcds.append(r)
    r_gcds = r_gcds[::-1]
    gcds = [l_gcds[-1], r_gcds[0]]
    for i in range(1, n - 1):
        gcds.append(gcd(l_gcds[i - 1], r_gcds[i]))
    print(max(gcds))
A, B, K = map(int, input().split())

ab = set(list(range(A,B+1,1)))
a = list(range(A,A+K,1))
b = list(range(B-K+1,B+1,1))
a.extend(b)
ans=a
ans = set(ans)
ans = list(ans&ab)
ans = sorted(ans)

for ansi in ans:
  print(ansi)


### FIXED CODE ###

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

for i in range(A,min([A+K+1,B+1]),1):
  if i<A+K:
    print(i)
    
for i in range(max([A+K, B-K-1]),B+1,1):
  if i>B-K:
    print(i)
from math import gcd
a,b = map(int,input().split())
print(gcd(a,b))

### FIXED CODE ###

a,b = map(int,input().split())
for i in range(b):
    if (a*(i+1))% b ==0:
        print(a*(i+1))
        break
s,t = map(str,input().split())
a,b = map(int,input().split())
u = str(input())

if s = u and not t = u:
    gap = a -1
    print(int(gap),b)
else:
    gap = b -1
    print(a,int(gap))s

### FIXED CODE ###

s,t = input().split()
a,b = map(int,input().split())
u = input()

if s == u:
    print(a -1,b)
else:
    print(a,b-1)
import numpy as numpy
from scipy.sparse.csgraph import floyd_warshall

N,M,L = map(int,input().split())
gurahu = np.zeros(N,N)

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

gurahu = floyd_warshall(gurahu, directed=False)
for s in range(N):
    for t in range(N):
        if gurahu[s][t] <= L:
            gurahu[s][t] = 0
        else:
            gurahu[s][t] = 1
gurahu = floyd_warshall(gurahu)

Q = int(input())

for k in range(Q):
    s,t = map(int,input().split())
    print(gurahu[s-1][t-1])

### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import floyd_warshall

N,M,L = map(int,input().split())
gurahu = np.zeros((N,N))

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

gurahu = floyd_warshall(gurahu, directed=False)
gurahu = np.where((gurahu <= L) & (gurahu > 0), 1, 0)
gurahu = floyd_warshall(gurahu) - np.ones((N, N))

Q = int(input())

for k in range(Q):
    s,t = map(int,input().split())
    ans = gurahu[s-1,t-1]
    if ans == float('inf'):
        print(-1)
    else:
        print(int(ans))
N,M = map(int,input().split())

A = [ list(map(int,input().split())) for _ in range(N) ]
A.sort()
ans = 0
for M == 0:
  if M >= A[0][1]:
    ans += A[0][0] * A[0][1]
    M -= A[0][1]
    del A[0]
  else:
    ans += A[0][0] * M
    M = 0
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
 
A = [ list(map(int,input().split())) for _ in range(N) ]
A.sort()
ans = 0
while M > 0:
  if M >= A[0][1]:
    ans += A[0][0] * A[0][1]
    M -= A[0][1]
    del A[0]
  else:
    ans += A[0][0] * M
    M = 0
print(ans)
a = int(input())
b = int(input())
c = int(input())
x = int(input())
answer = 0
for i in range(0,(a + 1)):
    for j in range(0,(b + 1)):
        for k in range(0,(c + 1)):
            if x == 500 * i + 100 * j + 50 * k:
                answer += 1
print(answer)

### FIXED CODE ###

x = int(input())
a = int(input())
b = int(input())
sub = x - a
while sub >= b:
    sub -= b
print(sub)
H, W , N = map(int,input().split())
from bisect import bisect_left
from bisect import bisect_right
matrix = []
for _ in range(N):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    matrix.append([x,y])
matrix.sort()
ans = [0 for _ in range(10)]
cand = {}
for l in matrix:
    for x_r in [-2, -1 , 0]:
        for y_r in [-2, -1 , 0]:
            nowx = l[0] + x_r
            nowy = l[1] + y_r
            if nowx < 0 or nowy < 0 or nowx + 2>= H or nowy+ 2 >= W:
                continue
            #ここで起点(左上)nowx, nowy として　 9マスに着目する
            name = str(nowx)  +str(nowy)
            try: cand[name] += 1
            except: cand[name] = 1
tmp = ((H - 2) * (W - 2))
for x in cand.values():
    ans[x] += 1
    tmp -= 1
ans[0] = tmp
for x in ans:
    print(x)


### FIXED CODE ###

H, W , N = map(int,input().split())
from bisect import bisect_left
from bisect import bisect_right
matrix = []
for _ in range(N):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    matrix.append([x,y])
matrix.sort()
ans = [0 for _ in range(10)]
cand = {}
for l in matrix:
    for x_r in [-2, -1 , 0]:
        for y_r in [-2, -1 , 0]:
            nowx = l[0] + x_r
            nowy = l[1] + y_r
            if nowx < 0 or nowy < 0 or nowx + 2>= H or nowy+ 2 >= W:
                continue
            #ここで起点(左上)nowx, nowy として　 9マスに着目する
            name = str(nowx) +"hoge" +str(nowy)
            try: cand[name] += 1
            except: cand[name] = 1
tmp = ((H - 2) * (W - 2))
for x in cand.values():
    ans[x] += 1
    tmp -= 1
ans[0] = tmp
for x in ans:
    print(x)
print((n // 2) * min(8 * q, 4 * h, 2 * s, d) + (n % 2) * min(4 * q, 2 * h, s))

### FIXED CODE ###

q, h, s, d = map(int, input().split())
n = int(input())
print((n // 2) * min(8 * q, 4 * h, 2 * s, d) + (n % 2) * min(4 * q, 2 * h, s))