Harryxun/stf_run huggingface dataset:
N, K = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N - 1)]
MOD = 10 ** 9 + 7

def dfs(u, par):
    color_num = K - 1 if par == -1 else K - 2

    if len(graph[u]) > K:
        return 0
    
    cnt = 1
    for v in graph[u]:
        if v == par:
            continue

        cnt *= color_num
        cnt %= MOD
        color_num -= 1

    for v in graph[u]:
        if v == par:
            continue

        cnt *= dfs(v, u)
        cnt %= MOD
        
    return cnt

graph = [[] for _ in range(N)]
for u, v in edges:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)

print(dfs(0, -1) * K % MOD)



### FIXED CODE ###

from collections import deque
N, K = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N - 1)]
MOD = 10 ** 9 + 7

def dfs(u, par):
    q = deque()
    q.append((u, par))
    ret = 1

    while q:
        u, par = q.pop()
        color_num = K - 1 if par == -1 else K - 2
        
        if len(graph[u]) > K:
            return 0
            
        for v in graph[u]:
            if v == par:
                continue
                
            ret *= color_num
            ret %= MOD
            color_num -= 1
            
            q.append((v, u))

    return ret

graph = [[] for _ in range(N)]
for u, v in edges:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)

print(dfs(0, -1) * K % MOD)
import math
a, b, c, d = map(int, input().split())
ans = b - (b//c)
ans -= b//d
ans += b//((c*d)//math.gcd(c, d))
x = (a-1)-((a-1)//c)
x -= (a-1)//d
x += (a-1)//((c*d)//math.gcd(c,d))
ans -= x
print(ans)


### FIXED CODE ###

import fractions
a, b, c, d = map(int, input().split())
ans = b - (b//c)
ans -= b//d
ans += b//((c*d)//fractions.gcd(c, d))
x = (a-1)-((a-1)//c)
x -= (a-1)//d
x += (a-1)//((c*d)//fractions.gcd(c,d))
ans -= x
print(ans)
a = [2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = list(map(int, input().split()))
A = sorted(set(list(map(int, input().split()))), reverse=True)
B = sorted([a[i-1] for i in A])

dp = [-1] * (N+1)
for b in B:
    dp[b] = 1

for i in range(1, N+1):
    for b in B:
        if i < b:
            break
        else:
            dp[i] = max(dp[i], dp[i-b]+1)
digit = dp[-1]

for n in A:
    x = a[n-1]
    while dp[N-x] == digit-1:
        print(n, end='')
        N -= x
        digit -= 1
    if N == x:
        print(n, end='')
        N -= x

### FIXED CODE ###

a = [2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = list(map(int, input().split()))
A = sorted(set(list(map(int, input().split()))), reverse=True)
B = sorted([a[i-1] for i in A])

dp = [-1] * (N+1)
for b in B:
    if b < N+1:
        dp[b] = 1

for i in range(1, N+1):
    for b in B:
        if i < b:
            break
        else:
            dp[i] = max(dp[i], dp[i-b]+1)
digit = dp[-1]

for n in A:
    x = a[n-1]
    if N-x >= 0:
        while dp[N-x] == digit-1:
            print(n, end='')
            N -= x
            digit -= 1
        if N == x:
            print(n, end='')
            N -= x
def shell_sort(array):
    n = len(array)
    h = 0
    k = 0
    cnt = 0
    g = []
    while h <= n/9:
        h = 3*h + 1
        g.append(h)
    while g[k] > 0:
        for i in range(h,n):
            tmp = array[i]
            if tmp < array[i-g[k]]:
                j = i
                while True:
                    array[j] = array[j-g[k]]
                    j -= h
                    c += 1
                    if j < h or tmp >= array[j-g[k]]:
                        break
                array[j] = tmp
    print(len(g))
    print(*g)
    for i in range(array): print(array[i])

d = []
for i in range(int(input())):
    d.append(int(input()))
shell_sort(d)
    


### FIXED CODE ###

def insertionSort(A,n,g):
    cnt = 0
    for i in range(g,n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
            A[j+g] = v
    return cnt
    
def shellsort(A,n):
    cnt = 0
    h = 1
    G = []
    while h <= n:
        G.append(h)
        h = 3*h + 1
    G.reverse()
    m = len(G)
    print(m)

    print(" ".join(map(str,G)))
    for i in range(m):
        cnt += insertionSort(A,n,G[i])
    print(cnt)
    for i in A:
        print(i)
        
n = int(input())
A = []
for _ in range(n):
    A.append(int(input()))
shellsort(A,n)
import math
x=int(input())
def eratosthenes(n):
    """n以下の素数をエラトステネスの篩によって求める.リストをかえす"""
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
ans=eratosthenes(10**5+3)
for i in  range(len(ans)):
	if ans[i]>=x:
    	print(ans[i])
	else:
      pass

### FIXED CODE ###

import math
x=int(input())
def eratosthenes(n):
    """n以下の素数をエラトステネスの篩によって求める.リストをかえす"""
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
ans=eratosthenes(10**5+3)
for i in  range(len(ans)):
    if ans[i]>=x:
        print(ans[i])
        exit()
    else:
        pass
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())




n,m=mi()
print("Yes"if n==m else "No")

### FIXED CODE ###

# from math import ceil,sqrt,log,gcd
# def ii():return int(input())
# def si():return input()
# def mi():return map(int,input().split())
# def li():return list(mi())




n,m=map(int,input().split())
if(n==m):
    print("Yes")
else:
    print('No')
n=int(input())
ans=0
for i in range(4):
  if n%10=2:
    ans+=1
  n=n/10
print(ans)

### FIXED CODE ###

n=int(input())
ans=0
for i in range(4):
  if int(n%10)==2:
    ans+=1
  n=n/10
print(ans)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Jan 12 22:19:09 2020

@author: nanasakiwataru
"""

def alphabet(C):
    ans = chr(ord(C) + 1)
    st = C + 'の次は'+ n + 'です。'
    return  st

n = alphabet('a')
print(n)



### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Jan 12 22:19:09 2020

@author: nanasakiwataru
"""

C = input()
ans = chr(ord(C) + 1)
print(ans)
import itertools as it 

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

l.sort()

triangles = set()
for a, b, c in it.combinations(l, 3):
    if a + b > c and b + c > a and a + c > b:
        triangles.add((a, b, c))

print(len(triangles))

### FIXED CODE ###

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

print(max(a - 2 * b, 0))
N, M = map(int, input().split())

visited = [0 for _ in range(N)]
graph = [[0] * M for _ in range(M)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1


def dfs(i, depth):
    if visited[i]:
        return 0
    if depth == N - 1:
        return 1

    visited[i] = 1
    ret = 0
    for j in range(0, N):
        if graph[i][j]:
            ret += dfs(j, depth + 1)

    visited[i] = 0

    return ret


print(dfs(0, 0))


### FIXED CODE ###

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)


def dfs(now, prev, visited):
    visited.append(now)
    if len(visited) == N:
        return 1

    ret = 0
    for edge in graph[now]:
        if edge == prev:
            continue
        if edge in visited:
            continue

        ret += dfs(edge, prev, visited[:])

    return ret


print(dfs(0, -1, []))
import sys
import math

def input():
    return sys.stdin.readline().rstrip()

def combination(n, r):
    return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

if __name__ == "__main__":
    n, k = map(int, input().split())

    for i in range(1, k+1):
        print((combination(n-k+1, i) * combination(k-1, i-1)) % (10**9+7))


### FIXED CODE ###

import sys
import math

def input():
    return sys.stdin.readline().rstrip()

def combination(n, r):
    return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

if __name__ == "__main__":
    n, k = map(int, input().split())

    for i in range(1, k+1):
        if n-k+1 >= i and k-1 >= i-1:
            print((combination(n-k+1, i) * combination(k-1, i-1)) % (10**9+7))
        else:
            print(0)
N,M = map(int,input().split())
homeworks = [int(i) for i in input().split()]
print(-1 if sum(homeworks) > N else sum(homeworks) - N))

### FIXED CODE ###

N,M = map(int,input().split())
homeworks = [int(i) for i in input().split()]
print(-1 if sum(homeworks) > N else N - sum(homeworks))
a=int(input())
print("Yes" if math.sqrt(a).is_integer() else "No")

### FIXED CODE ###

import math
a,b=input().split()
n=int(a+b)
print("Yes" if math.sqrt(n).is_integer() else "No")
c1 = input()
c2 = input()
print('Yes' if c1 == c2.reverse() else 'No')

### FIXED CODE ###

c1 = list(input())
c2 = list(input())
c1.reverse()
print('YES' if c1 == c2 else 'NO')
nums = [int(i) for i in input().split()]

A = num[0]
B = num[1]
C = num[2]
 
temp = C - (A - B)
if temp < 0:
  temp = 0
  
print(temp)

### FIXED CODE ###

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

A = num[0]
B = num[1]
C = num[2]
 
temp = C - (A - B)
if temp < 0:
  temp = 0
  
print(temp)
n = int(input())
a = list(map(int, input().split()))
b = dict()
for i in range(n):
    b[i+1] = 0

for i in range(n):
    b[a[i]+1] += 1

for i in range(n):
    print(b[i+1])

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = dict()
for i in range(n):
    b[i+1] = 0

for i in range(n-1):
    b[a[i]] += 1

for i in range(n):
    print(b[i+1])
rates  = [399,799,1199,1599,1999,2399,2799,3199]
from collections import defaultdict


def return_index(score):
  for i in rates:
    if score <= i:
      return rates.index(i)
  else:
    return 8

N = int(input())
A = list(map(int,input().split()))
d = defaultdict(int)
for a in A:
  d[return_index(a)] += 1
num_of_9s = d[8]
has_9 = 1 if num_of_9s > 0 else 0
print("{} {}".format(len(d.keys()-has_9 ),len(d.keys())-has_9+num_of_9s ))

### FIXED CODE ###

rates  = [399,799,1199,1599,1999,2399,2799,3199]
from collections import defaultdict


def return_index(score):
  for i in rates:
    if score <= i:
      return rates.index(i)
  else:
    return 8

N = int(input())
A = list(map(int,input().split()))
d = defaultdict(int)
for a in A:
  d[return_index(a)] += 1
key_len = len(d.keys())
num_of_9s = d[8]
has_9 = 1 if num_of_9s > 0 else 0
print("{} {}".format(max(1,key_len-has_9),key_len-has_9+num_of_9s ))
import sys
n = int(input())
h = list(map(int,input().split()))
d = [0]*(n-1)
cmd = [0]*(n-1)

for i in range(n-1):
  d[i]= h[i+1]-h[i]

m = 0
 
if n==1:
  print("Yes")
  sys.exit()
  
elif min(d) <= -2:
  print("No")
  sys.exit()

else:
  for i in range(n-1):
    if h[i] == h[i+1]:
      cmd[i] == 0
    elif h[i]+1 == h[i+1] and cmd[i]==1:
      print("No")
      sys.exit()
    elif h[i]+1 == h[i+1] and cmd[i]==0:
      cmd[i+1] == 1  
  print("Yes")      
      
  
     

### FIXED CODE ###

import sys
n = int(input())
h = list(map(int,input().split()))
mi = h[0]-1
if n == 1:
  print("Yes")
  sys.exit()
  
for i in range(1,n):
  if h[i-1]-1 == h[i]:
    if mi > h[i]:
      print("No")
      sys.exit()
    mi = h[i]
  elif h[i-1] > h[i]:
    print("No")
    sys.exit()
    
print("Yes")
def main():
    N = int(input())
    cases = dict()
    for _ in range(N):
        s = input()
        cases[s] = cases.get(s, 0) + 1
    
    results = ["AC", "WA", "TLE", "RE"]

    for r in results:
        print(f"{r} x {cases[r]}")
    

if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    N = int(input())
    cases = dict()
    for _ in range(N):
        s = input()
        cases[s] = cases.get(s, 0) + 1
    
    results = ["AC", "WA", "TLE", "RE"]

    for r in results:
        print(f"{r} x {cases.get(r, 0)}")
    

if __name__ == '__main__':
    main()
n = int(input())
w = [int(i) for i in input().split()]
d = [abs(w[:i]-w[i:]) for i in range(1, n-1)]
print(min(d))

### FIXED CODE ###

n = int(input())
w = [int(i) for i in input().split()]
d = [abs(sum(w[:i])-sum(w[i:])) for i in range(1, n)]
print(min(d))
import math
n=int(input())
SN = 0
for i in range(1,math.ceil(math.log(n,10))+1):
  SN = SN + math.floor(n%(10**i)/(10**(i-1)))
print(SN)
if n%SN==0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

S=str(input())
total = 0
for i in range(len(S)):
  total = total + int(S[i])
if int(S)%total==0:
  print('Yes')
else:
  print('No')
def modpow(x,p,mod):
    ret=1
    for i in range(64):
        if (1<<i)&p:
            ret=ret*x%mod
        x=x*x%mod
    return ret

def inverse_table(n,mod):
    table=[]
    for i in range(0,n+1):
        table.append(modpow(i,mod-2,mod))
    return table

def factorial_table(n,mod):
    table=[1]
    for i in range(1,n+1):
        table.append(table[-1]*i%mod)
    return table


it=inverse_table(10**5,1000000007)
ft=factorial_table(10**5,1000000007)

def c(n,k,it,ft,mod):
    return ft[n]*it[ft[k]]*it[ft[(n-k)]]%mod

n,k=map(int,input().split())
a=sorted(map(int,input().split()))
hoge=[]
while True:
    hoge.append(c(n-1,k-1,it,ft,1000000007))
    if n-1==k-1:
        break
    n-=1
ans=0
for i in range(len(hoge)):
    ans-=hoge[i]*a[i]%1000000007
    ans+=hoge[i]*a[-i-1]%1000000007
    ans%=1000000007
print(ans)



### FIXED CODE ###

def modpow(x,p,mod):
    ret=1
    for i in range(64):
        if (1<<i)&p:
            ret=ret*x%mod
        x=x*x%mod
    return ret

def inverse_table(n,mod):
    table=[]
    for i in range(0,n+1):
        table.append(modpow(i,mod-2,mod))
    return table

def factorial_table(n,mod):
    table=[1]
    for i in range(1,n+1):
        table.append(table[-1]*i%mod)
    return table

def inverse_factorial_table(n,it,mod):
    table=[1]
    for i in range(1,n+1):
        table.append(table[-1]*it[i]%mod)
    return table

it=inverse_table(10**5,1000000007)
ft=factorial_table(10**5,1000000007)
ift=inverse_factorial_table(10**5,it,1000000007)
def c(n,k,it,ft,mod):
    return ft[n]*ift[k]*ift[(n-k)]%mod
n,k=map(int,input().split())
a=sorted(map(int,input().split()))
hoge=[]
while True:
    hoge.append(c(n-1,k-1,it,ft,1000000007))
    if n-1==k-1:
        break
    n-=1
ans=0
for i in range(len(hoge)):
    ans-=hoge[i]*a[i]%1000000007
    ans+=hoge[i]*a[-i-1]%1000000007
    ans%=1000000007
print(ans)
N = int(input())
H = list(map(int, input().split()))
ans = 1
for i,j,k in zip(H,H[1::],H[2::]):
    if i == j:
        if j > k:
            ans *= 0
    else i > j+1:
        ans *= 0
print("Yes" if ans == 1 else "No")


### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
for i in reversed(range(N-1)):
    if H[i]>H[i+1]:
        H[i] -= 1
        if H[i]>H[i+1]:
            print("No")
            exit()
print("Yes")
import collections
import numpy as np

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

A = np.array(A,dtype='int64')
C = np.append([0],np.cumsum(A))
#累積和を算出して最初に０をつける。
L = [i%M for i in C]
#Ｍで割ったあまりを求めてリスト化
d = defaultdict(int)
for i in L:
    d[i] +=1
#各余りに対して、その数が何個あるかを求める。

ans = 0
for i in d.values():
    S = i * (i-1) / 2
    ans+=S
    
print(int(ans))

### FIXED CODE ###

import collections
import numpy as np

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

A = np.array(A,dtype='int64')
C = np.append([0],np.cumsum(A))
L = [i%M for i in C]
L_c = collections.Counter(L)

ans = 0
for i in L_c.values():
    S = i * (i-1) / 2
    ans+=S
    
print(int(ans))
import heapq
N,M=(int(i) for i in input().split())



tasks=[[] for i in range(10**5+1)]
for i in range(N):
    a,b=(int(i) for i in input().split())
    tasks[a-1].append(b)

pq=[]
ans=0
for i in range(M):
    for b in tasks[i]:
        heappush(pq,b)
    if len(pq)!=0:
        ans+=heappop(pq)

print(ans)



### FIXED CODE ###

import heapq
N,M=(int(i) for i in input().split())



tasks=[[] for i in range(10**5+1)]
for i in range(N):
    a,b=(int(i) for i in input().split())
    tasks[a-1].append(b)

pq=[]
ans=0
for i in range(M):
    for b in tasks[i]:
        heapq.heappush(pq,-b)
    if len(pq)!=0:
        temp=heapq.heappop(pq)
        ans-=temp

print(ans)
setting = input().rstrip().split(" ")
N = int(setting[0])
Y = int(setting[1])


for x in range(N):
    for y in range(N):
        if 10000*x + 5000*y + 1000*(N-x-y) == Y :
            otoshidama = [x,y,N-x-y]
        else:
            pass

print(otoshidama[0]," ",otoshidama[1]," ",otoshidama[2])   

### FIXED CODE ###

S = input()
S=S.replace("2017","2018")

print(S)
s = input().split()
N = int(s[0])
K = int(s[1])

ans = N // K 

if K % 2 == 0:
  ans = ans + N//(K%2)

print(ans**3 ) 

### FIXED CODE ###

s = input().split()
N = int(s[0])
K = int(s[1])

ans = N // K 
ans = ans ** 3

ans_ev = 0
if K % 2 == 0:
  ans_ev = (N+(K//2)) // (K)
  ans_ev = ans_ev ** 3
                         

print(ans+ ans_ev )
import math
a = int(input())
b = int(input())
h = int(input())
m = int(input())
x = (h*60+m)/2  
y = 6*m   
angle = abs(x - y)  
angle = min(360 - angle, angle) 
pi = 3.14159265358979323
k = math.pi/180
if angle==180:
    print(a+b)
    
elif(angle==0):
    print(0.0000000000)
    
else:
    angle = angle*k
    p = math.cos(angle)
    if(p<-1):
        p=0
    ans=pow(a,2)+pow(b,2)- 2*a*b*p;
    ans = math.sqrt(ans);
    print(ans)

### FIXED CODE ###

import math
a,b,h,m = [int(x) for x in input().split()] 
x = (h*60+m)/2  
y = 6*m   
angle = abs(x - y)  
angle = min(360 - angle, angle) 
pi = 3.14159265358979323
k = math.pi/180
if angle==180:
    print(a+b)
    
elif(angle==0):
    print(abs(a-b))
    
else:
    angle = angle*k
    p = math.cos(angle)
    if(p<-1):
        p=0
    ans=pow(a,2)+pow(b,2)- 2*a*b*p;
    ans = math.sqrt(ans);
    print(ans)
# PROXY

import functools
import math
N = int(input())
Nlist = [int(i) for i in input().split()]
gcd = functools.reduce(math.gcd, Nlist)
print(gcd)

### FIXED CODE ###

# PROXY

import functools
import fractions
N = int(input())
Nlist = [int(i) for i in input().split()]
gcd = functools.reduce(fractions.gcd, Nlist)
print(gcd)
import sys

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    if H == 1 or W == 1: print(1)
    else: Ans = (H // 2 + H % 2) * (W // 2 + W % 2) + (H // 2) *  (W // 2)
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    if H == 1 or W == 1: print(1)
    else: 
        Ans = (H // 2 + H % 2) * (W // 2 + W % 2) + (H // 2) *  (W // 2)
        print(Ans)

    return 0

if __name__ == "__main__":
    solve()
import numpy as np

n, m = map(int, input().split())
h = np.array(list(map(int, input().split())))
nets = np.zeros((n,n))

for i in range(m):
    a,b = map(int, input().split())
    nets[a - 1][b - 1] = h[b-1]
    nets[b - 1][a - 1] = h[a-1]

ans = 0

#print(nets)

for i in range(n):
    if (h[i] >max(nets[i])):
        ans += 1

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
nets = [0]*n

for _ in range(m):
    a,b = map(int, input().split())
    nets[a - 1] = max(nets[a-1], h[b-1])
    nets[b - 1] = max(nets[b-1], h[a-1])

ans = 0

#print(nets)

for i in range(n):
    if (h[i] >nets[i]):
        ans += 1

print(ans)
import sys

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

if k==0:
    print(max(a))
    sys.exit()

def rf(mm):
    icnt=0
    for i in range(n):
        icnt+=(a[i]-1)//mm+1
    return icnt

asum=sum(a)
m=asum//(n+k)
um=asum
lm=1
for ii in range(60):
    if rf(m)<=(n+k) and rf(m-1)>(n+k):
        break
    if um-lm<5:
        break
    if rf(m)>(n+k):
        lm=m
        m=int((um+lm)//2)-1
    elif rf(m)<(n+k):
        um=m
        m=int((um+lm)//2)+1
    else:
        um=m-1
        m=int((um+lm)//2)
#    if rf(m)==(n+k) and um-lm<5:

for mi in range(um,max(0,lm-1),-1):
#for mi in range(m+5,max(0,m-10),-1):
    if rf(mi)<=(n+k) and rf(mi-1)>(n+k):
#    if rf(mi)!=rf(mi-1):
        break

print(mi)



### FIXED CODE ###

import sys

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

if k==0:
    print(max(a))
    sys.exit()

def rf(mm):
    if mm==0:
        mm=1
    icnt=0
    for i in range(n):
        icnt+=(a[i]-1)//mm+1
    return icnt

asum=sum(a)
m=asum//(n+k)
um=asum
lm=1
for ii in range(60):
    if m==1:
        break
    if rf(m)<=(n+k) and rf(m-1)>(n+k):
        break
    if um-lm<5:
        break
    if rf(m)>(n+k):
        lm=m
        m=(um+lm)//2-1
    elif rf(m)<(n+k):
        um=m
        m=(um+lm)//2-1
    else:
        um=m-1
        m=(um+lm)//2-1
#    if rf(m)==(n+k) and um-lm<5:

if um<1:
    print(1)
    sys.exit()
    
for mi in range(um,max(0,lm-1),-1):
    if rf(mi)<=(n+k) and rf(mi-1)>(n+k):
        break

print(mi)
from fractions import gcd
from functools import reduce
import sys


def lcm_base(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


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

max_value = 2 * m

lcm = lcm_list(A)

if any((lcm / a) % 2 != 1 for a in A):
    print("0")
    sys.exit(0)

max_product = max_value // lcm
print((max_product + 1) // 2)


### FIXED CODE ###

from fractions import gcd
from functools import reduce
import sys


def lcm_base(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers, maxvalue):
    first = 1
    second = 1
    for i in numbers:
        second = i
        lcm_result = lcm_base(first, second)
        if lcm_result > max_value:
            return -1
        first = lcm_result
    return lcm_result


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

max_value = 2 * m

lcm = lcm_list(A, 2 * m)
if lcm == -1:
    print("0")
    sys.exit(0)

if any((lcm / a) % 2 != 1 for a in A):
    print("0")
    sys.exit(0)

max_product = max_value // lcm
print((max_product + 1) // 2)
N,M = map(int,input().split())
S = []
C = []
for i in range(M):
    temp1,temp2 = map(int,input().split())
    S.append(temp1)
    C.append(temp2)

Flag = True
temp = [-1,-1,-1]
for i in range(M):
    if S[i] == 3:
        if temp[2] == -1:
            temp[2] = C[i]
        else:
            if temp[2] == C[i]:
                next
            else:
                Flag = False

for i in range(M):
    if S[i] == 2:
        if temp[1] == -1:
            temp[1] = C[i]
        else:
            if temp[1] == C[i]:
                next
            else:
                Flag = False

for i in range(M):
    if S[i] == 1:
        if temp[0] == -1:
            temp[0] = C[i]
        else:
            if temp[0] == C[i]:
                next
            else:
                Flag = False

a = ''
if Flag == False:
    print(-1)
elif temp[0] ==0:
    print(-1)
elif temp[2] == -1:
    if temp[1] == -1:
        print(temp[0])
    elif temp[0] == -1:
        print(int(str(1) + str(temp[1])))
    else:
        if temp[0] == 0:
            print(-1)
        else:
            print(int(str(temp[0]) + str(temp[1])))
else:
    if temp[0] == -1 and temp[1] == -1:
        print(temp[2])
    elif temp[0] == -1 and temp[1] != -1:
        if temp[0] == 0:
            print(-1)
        else:
            print(int(str(temp[1]) + str(temp[2])))
    elif temp[0] != -1 and temp[1] == -1:
        if temp[0] == 0:
            print(-1)
        else:
            print(int(str(temp[0]) + str(0) + str(temp[2])))
    else:
        if temp[0] == 0:
            print(-1)
        else:
            print(int(str(temp[0]) + str(temp[1]) + str(temp[2])))

### FIXED CODE ###

N = int(input())

if N % 2 == 1:
    print(N//2 + 1)
else:
    print(N//2)