Harryxun/stf_run huggingface dataset:
import sys
#from collections import defaultdict, deque, Counter
#from bisect import bisect_left
#import heapq
import math
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

#n = int(stdin.readline().rstrip())
#l = list(map(int, stdin.readline().rstrip().split()))
a,b,c,d = map(int, stdin.readline().rstrip().split())
#S = [list(stdin.buffer.readline().decode().rstrip()) for _ in range(h)]

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

# 最小公倍数
cd = lcm(c,d)

# b以下
cwari = b//c
dwari = b//d
cdwari = b//cd
ub = b-cwari-dwari+cdwari

# a以下
cwari = a//c
dwari = a//d
cdwari = a//cd
ua = a-cwari-dwari+cdwari

if a%c != 0 and a%d !=0:
    print(ub-ua+1)
else:
    print(ub-ua)


### FIXED CODE ###

import sys
#from collections import defaultdict, deque, Counter
#from bisect import bisect_left
#import heapq
#import math
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

#n = int(stdin.readline().rstrip())
#l = list(map(int, stdin.readline().rstrip().split()))
a,b,c,d = map(int, stdin.readline().rstrip().split())
#S = [list(stdin.buffer.readline().decode().rstrip()) for _ in range(h)]

def gcd(a,b):
  while b:
    a,b = b,a%b
  return a

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


cd = lcm(c,d)

# b以下
cwari = b//c
dwari = b//d
cdwari = b//cd
ub = b-cwari-dwari+cdwari

# a以下
cwari = (a-1)//c
dwari = (a-1)//d
cdwari = (a-1)//cd
ua = (a-1)-cwari-dwari+cdwari

print(ub-ua)
N = int(input())
list1 = [(input() + " " + str(i+1)).split() for i in range(N)]
 
list1 = [a for a in lis]
 
list1.sort(key=lambda a: int(a[1]), reverse=True)
list1.sort(key=lambda a: a[0])
 
 
for i in lis:
    print(i[2])

### FIXED CODE ###

try:
    a,p=map(int, input().split())
    assert 0<=a,p<=100
    print(((a*3)+p)//2)
except AssertionError:
    print('')
N,M=map(int,input().split())
sc=[list(map(int,input().split())) for i in range(M)]
s=[]
c=[]
for i in range(M):
  s.append(sc[i][0]-1)
  c.append(sc[i][1])

S=[s[0]]
C=[c[0]]
for i in range(1,M):
  if s[i] in S:
    if C[S.index(s[i])]==c[i]:
      continue
    else:
      print('-1')
      exit()
  else:
    S.append(s[i])
    C.append(c[i])

ans=[0]*(N)
ans[0]=1

for i in range(M):
  ans[s[i]]=c[i]

if len(ans)!=0 and ans[0]==0:
  print('-1')
  exit()

ANS=""
for i in range(N):
  ANS+=str(ans[i])
print(ANS)

### FIXED CODE ###

N,M=map(int,input().split())
sc=[list(map(int,input().split())) for i in range(M)]
if N==1:
  start=0
else:
  start=10**(N-1)

for i in range(start,10**N):
  n=str(i)
  cnt=0
  for j in range(M):
    if n[sc[j][0]-1]==str(sc[j][1]):
      cnt+=1
    else:
      break
  if cnt==M:
    print(n)
    exit()
print('-1')
from typing import Optional
import sys


def dfs(i: int, s: str, val: int, formula: str) -> Optional[str]:
    if (i == len(s) - 1):
        if val == 7:
            print(formula + "=7")
            sys.exit()
            return formula
        else:
            return None

    dfs(i + 1, s, val + int(s[i + 1]), formula + "+" + s[i + 1])
    dfs(i + 1, s, val - int(s[i + 1]), formula + "-" + s[i + 1])
    return None


s = input()
ans = dfs(0, s, int(s[0]), s[0])


### FIXED CODE ###

import sys


def dfs(i, s, val, formula):
    if (i == len(s) - 1):
        if val == 7:
            print(formula + "=7")
            sys.exit()
            return formula
        else:
            return None

    dfs(i + 1, s, val + int(s[i + 1]), formula + "+" + s[i + 1])
    dfs(i + 1, s, val - int(s[i + 1]), formula + "-" + s[i + 1])
    return None


s = input()
ans = dfs(0, s, int(s[0]), s[0])
N=int(input())
if N%2==0:
  print(N//2,N,N)
else:
  for i in range(1,3501):
    for j in range(1,3501):
      if 4*i*j-N*i-N*j>0 and (N*i*j)/(4*i*j-N*i-N*j).is_integer():
          print(i,j,int(w))
          exit()

### FIXED CODE ###

N=int(input())
if N%2==0:
  print(N//2,N,N)
else:
  for i in range(1,3501):
    for j in range(1,3501):
      if 4*i*j-N*i-N*j!=0:
        w=(N*i*j)/(4*i*j-N*i-N*j)
        if w>0 and w.is_integer():
          print(i,j,int(w))
          exit()
from itertools import combinations
from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 6)
 

def main():
    # dp:=上からi桁目まで払える最小の枚数
    S = list(map(int, input()))
    l = len(S)
    dp = [[1e18]*2 for _ in range(10**6)]
    dp[0][0]=0
    for i in range(l):
        k = int(S[i])
        dp[i+1][0] = min(dp[i+1][0], dp[i][0]+k)
        dp[i+1][1] = min(dp[i+1][1], dp[i][0]+k+1)
        dp[i+1][0] = min(dp[i+1][0], dp[i][1]+10-k)
        dp[i+1][1] = min(dp[i+1][1], dp[i][1]+10-k-1)
    print(dp[l][0])

    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
def main():
    # dp:=上からi桁目まで払える最小の枚数
    S = list(map(int, '0'+input()))
    l = len(S)
    dp = [[1e18]*2 for _ in range(1001001)]
    dp[0][0]=0
    for i in range(l):
        k = S[i]
        dp[i+1][0] = min(dp[i+1][0], dp[i][0]+k)
        dp[i+1][1] = min(dp[i+1][1], dp[i][0]+k+1)
        dp[i+1][0] = min(dp[i+1][0], dp[i][1]+10-k)
        dp[i+1][1] = min(dp[i+1][1], dp[i][1]+10-k-1)
    print(dp[l][0])

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

s = input()
x_goal, y_goal = map(int, input().split())

directed_x = None
steps = 0
xs = [0]
ys = [0]
for c in (s+'T'):   #sentinel
    if c == 'F':
        steps += 1
    else:
        if directed_x is None:
            x_goal -= steps
            directed_x = True
        elif steps != 0:
            if directed_x:
                xs.append(steps)
            else:
                ys.append(steps)
        steps = 0
        directed_x = not directed_x

dx_2 = sum(xs) - x_goal
if dx_2 % 2 == 1:
    ans = False
else:
    dx = dx_2 // 2
    possible_x = np.full(dx + 1, False)
    possible_x[0] = True
    for x in xs:
        possible_x[x:] = np.logical_or(possible_x[:len(possible_x)-x], possible_x[x:])
        if possible_x[dx]:
            ans = True
            break
    else:
        ans = False

if ans:
    dy_2 = sum(ys) - y_goal
    if dy_2 % 2 == 1:
        ans = False
    else:
        dy = dy_2 // 2
        possible_y = np.full(dy + 1, False)
        possible_y[0] = True
        for y in ys:
            possible_y[y:] = np.logical_or(possible_y[:len(possible_y)-y], possible_y[y:])
            if possible_y[dy]:
                ans = True
                break
        else:
            ans = False

if ans:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import numpy as np

s = input()
x_goal, y_goal = map(int, input().split())

directed_x = None
steps = 0
xs = [0]
ys = [0]
for c in (s+'T'):   #sentinel
    if c == 'F':
        steps += 1
    else:
        if directed_x is None:
            x_goal -= steps
            directed_x = True
        elif steps != 0:
            if directed_x:
                xs.append(steps)
            else:
                ys.append(steps)
        steps = 0
        directed_x = not directed_x

dx_2 = sum(xs) - x_goal
if dx_2 % 2 == 1 or dx_2 < 0:
    ans = False
else:
    dx = dx_2 // 2
    possible_x = np.full(dx + 1, False)
    possible_x[0] = True
    for x in xs:
        possible_x[x:] = np.logical_or(possible_x[:len(possible_x)-x], possible_x[x:])
        if possible_x[dx]:
            ans = True
            break
    else:
        ans = False

if ans:
    dy_2 = sum(ys) - y_goal
    if dy_2 % 2 == 1 or dy_2 < 0:
        ans = False
    else:
        dy = dy_2 // 2
        possible_y = np.full(dy + 1, False)
        possible_y[0] = True
        for y in ys:
            possible_y[y:] = np.logical_or(possible_y[:len(possible_y)-y], possible_y[y:])
            if possible_y[dy]:
                ans = True
                break
        else:
            ans = False

if ans:
    print("Yes")
else:
    print("No")
import sys
input = sys.stdin.readline()
H,N = map(int,input().split())
spells = [list(map(int,input().split())) for i in range(N)]
INF = 10**10
dp = [INF]*(H+1)
dp[0] = 0
for use in spells:
    damage = use[0]
    mp = use[1]
    for i in range(1,H+1):
        dp[i] = min(dp[max(0,i-damage)] + mp, dp[i])
print(dp[-1])


### FIXED CODE ###

h,n=map(int,input().split())
mahou=[list(map(int,input().split())) for i in range(n)]
INF=10**10
dp=[INF]*(h+1)#そのHPを与えるのに必要な最小MP
dp[0]=0
for hp in range(h+1):
  for use in mahou:
    dp[hp]=min(dp[max(0,hp-use[0])]+use[1],dp[hp])
print(dp[h])
H, W = map(int, input().split()) 
h, w = map(int, input(.split()))
print((H-h) * (W - w))


### FIXED CODE ###

H, W = map(int, input().split()) 
h, w = map(int, input().split())
print((H-h) * (W - w))
n=int(input())
l=list(map(int,input().split()))

cnt=0

if l[0]>l[1]:
  ans="low"
elif l[0]<l[1]:
  ans="high"
else:
  ans="even"
  
for i in range(2,n):
  if l[i-1]>l[i] and (ans=="low" or ans=="even"):
    ans="low"
  elif l[i-1]<l[i] and (ans=="high" or ans=="even"):
    ans="high"
  elif l[i-1]==l[i]:
    ans="even"
  else:
    cnt+=1
    ans="even"
    
print(cnt+1)

### FIXED CODE ###

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

if n<=2:
  print(1)
  exit()
  
cnt=0

if l[0]>l[1]:
  ans="low"
elif l[0]<l[1]:
  ans="high"
else:
  ans="even"
  
for i in range(2,n):
  if l[i-1]>l[i] and (ans=="low" or ans=="even"):
    ans="low"
  elif l[i-1]<l[i] and (ans=="high" or ans=="even"):
    ans="high"
  elif l[i-1]==l[i]:
    continue
  else:
    cnt+=1
    ans="even"
    
print(cnt+1)
#組み合わせ、コンビネーション
def cmb(n,r):
  	if n ==1:
      return 0
    else:
      r=min(r,n-r)
      result=1
      for i in range(n-r+1,n+1):
          result*=i
      for i in range(1,r+1):
          result//=i
      return result

#素因数分解、辞書を返す
def factorize(n):
    i=2
    result={}
    while True:
        if i**2>n:
            break
        count=0
        while n%i==0:
            n//=i
            count+= 1
        if count!=0:
            result[i]=count
        i+=1
    if n>1:
        result[n]=1
    return result

N = int(input())
l={}
for i in range(1,N+1):
    for i,j in factorize(i).items():
        l[i] = l.get(i,0)+j


l2 = [0]*5

r = 0
for j,i in l.items():
    if i>=74:
        l2[4]+=1
    elif i>=24:
        l2[3]+=1
    elif i>=14:
        l2[2]+=1
    elif i>=4:
        l2[1]+=1
    elif i>=2:
        l2[0]+=1
# print(l)
# print(l2)

r += l2[4]
r += sum(l2[3:])*(sum(l2)-1)
r += sum(l2[2:])*(sum(l2[1:])-1)
r += cmb(sum(l2[1:]),2)*(sum(l2)-2)
print(r)

### FIXED CODE ###

#組み合わせ、コンビネーション
def cmb(n,r):
    if n==0:return 0
    else:
        r=min(r,n-r)
        result=1
        for i in range(n-r+1,n+1):
            result*=i
        for i in range(1,r+1):
            result//=i
        return result

#素因数分解、辞書を返す
def factorize(n):
    i=2
    result={}
    while True:
        if i**2>n:
            break
        count=0
        while n%i==0:
            n//=i
            count+= 1
        if count!=0:
            result[i]=count
        i+=1
    if n>1:
        result[n]=1
    return result

N = int(input())
l={}
for i in range(1,N+1):
    for i,j in factorize(i).items():
        l[i] = l.get(i,0)+j


l2 = [0]*5

r = 0
for j,i in l.items():
    if i>=74:
        l2[4]+=1
    elif i>=24:
        l2[3]+=1
    elif i>=14:
        l2[2]+=1
    elif i>=4:
        l2[1]+=1
    elif i>=2:
        l2[0]+=1

r += l2[4]
r += sum(l2[3:])*(sum(l2)-1)
r += sum(l2[2:])*(sum(l2[1:])-1)
r += cmb(sum(l2[1:]),2)*(sum(l2)-2)
print(r)
n = iint(input())
ls = []
for i in range(1,n+1):
  s,p = input().split()
  ls.append([i,s,int(p)])
ls.sort(key=lambda x:(x[1], x[2]))
for j in range(len(ls)):
  print(ls[j][0])

### FIXED CODE ###

n = int(input())
ls = []
for i in range(1,n+1):
    s,p = input().split()
    ls.append([i,s,int(p)])
ls.sort(key=lambda x:(x[1], -x[2]))
for j in range(len(ls)):
    print(ls[j][0])
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, k、*a = map(int, read().split())
v = 0
ans = 0
for i in range(40, -1, -1):
    cnt = 0
    for aa in a:
        if aa >> i & 1:
            cnt += 1
    if n - cnt > cnt and v + 1 << i <= k:
        v += 1 << i
        ans += (n - cnt) * 1 << i
    else:
        ans += cnt * 1 << i
print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, k, *a = map(int, read().split())
v = 0
ans = 0
for i in range(40, -1, -1):
    cnt = 0
    for aa in a:
        if (aa >> i) & 1:
            cnt += 1
    if n - cnt > cnt and v + (1 << i) <= k:
        v += 1 << i
        ans += (n - cnt) * (1 << i)
    else:
        ans += cnt * (1 << i)
print(ans)
a,b,c=sorted(map(int,input()))
print(10*c+a+b)


### FIXED CODE ###

a,b,c=sorted(map(int,input().split()))
print(10*c+a+b)
import math as M
def R(A): return (A[0]**2+A[1]**2)**.5
def I(i): return [map(int,raw_input().split()) for _ in [0]*i]
def C(a,b): return a>b or abs(a-b)<1e-6
def f(e1):
  tx,ty,sx,sy=e1
  x=[]
  for e2 in WP:
    wx,wy,r=e2
    wt=[tx-wx,ty-wy]; rwt=R(wt)
    sw=[wx-sx,wy-sy]; rsw=R(sw)
    st=[tx-sx,ty-sy]; rst=R(st)
    F=[rwt<r,rsw<r]
    if rst==0: c=1
    elif F==[1,1]: c=1 # 両方壁の中
    elif F==[1,0] or F==[0,1]: c=0 # 片方が壁の中
    elif F==[0,0]: #両方壁の外
      a=M.pi/2-M.acos(r/rsw)
      tmp=0#(sw[0]*st[0]+sw[1]*st[1])/rsw/rst
      if abs(abs(tmp)-1)<1e-6: tmp=1
      b=0#M.acos(tmp/2)
      if C(a,b) and C(rst**2,rsw**2-r**2): c=0
      else: c=1
    x.append(c)
  return all(x)

while 1:
  n=input()
  if n==0: break
  WP=I(n)
  P=I(input())
  for e in P: print ["Safe","Danger"][f(e)]

### FIXED CODE ###

import math as M
def R(A): return (A[0]**2+A[1]**2)**.5
def I(i): return [map(int,raw_input().split()) for _ in [0]*i]
def C(a,b): return a>b or abs(a-b)<1e-6
def f(e1):
  tx,ty,sx,sy=e1
  x=[]
  st=[tx-sx,ty-sy]; rst=R(st)
  for e2 in WP:
    wx,wy,r=e2
    wt=[tx-wx,ty-wy]; rwt=R(wt)
    sw=[wx-sx,wy-sy]; rsw=R(sw)
    F=[rwt<r,rsw<r]
    if F==[1,0] or F==[0,1]: return 0
    elif F==[0,0]:
      a=M.pi/2-M.acos(r/rsw)
      b=M.acos(round((sw[0]*st[0]+sw[1]*st[1])/rsw/rst,4))
      if C(a,b) and C(rst**2,rsw**2-r**2): return 0
  return 1

while 1:
  n=input()
  if n==0: break
  WP=I(n)
  P=I(input())
  for e in P: print ["Safe","Danger"][f(e)]
n, m = map(int, input().split())

img = [input() for i in range(n)]
template = [input() for i in range(m)]

for i in range(n - m + 1):
    if len({v.index(t) for v, t in zip(img[i:i + m], template)}) == 1:
        print("Yes")
        break
else:
    print("No")


### FIXED CODE ###

import numpy as np
n, m = map(int, input().split())

img = np.array([list(input()) for i in range(n)])
w = img.shape[-1]
template = np.array([list(input()) for i in range(m)])
tw = template.shape[-1]

for y in range(n - m + 1):
    for x in range(w - tw + 1):
        if np.all(img[y:y + m, x:x + tw] == template):
            print("Yes")
            exit()
print("No")
N, W = (int(i) for i in input().split())
w = [0]*N
w0 = w[0]
wh = [a - w0 for a in W]
v = [0]*N
for i in range(N):
  w[i], v[i] = (int(i) for i in input().split())
dp = [[[0]*(N+1) for i in range(3N+1)] for j in range(N+1)]
for i in range(N):
  for j in range(3N+1):
    for k in range(N+1):
      dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
      if j - wh[i] >=0 and k-1 >=0:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-wh[i]][k-1]+v[i])
res = 0
for k in range(N+1):
  if w0*k <= W <= (w0+3)*k:
    Wk = W - w0*k
    ans = 0
    for j in range(Wk+1):
      ans = max(dp[N][j][k], ans)
    res = max(res, ans)
print(res)

### FIXED CODE ###

N, W = (int(i) for i in input().split())
w = [0]*N
v = [0]*N
for i in range(N):
  w[i], v[i] = (int(j) for j in input().split())
w0 = w[0]
wh = [a - w0 for a in w]
dp = [[[-1]*(N+1) for i in range(3*N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
  for j in range(3*N+1):
    for k in range(N+1):
      if dp[i][j][k] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
      if j - wh[i] >=0 and k-1 >=0 and dp[i][j-wh[i]][k-1] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-wh[i]][k-1]+v[i])
res = 0
for j in range(3*N+1):
  for k in range(N+1):
    if j + w0*k <= W:
      res = max(dp[N][j][k], res)
print(res)
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

x=int(readline())
def a(n):
  for i in range(2, int(n ** 0.5 + 1)):
    if n % i == 0:
      return False
  return True
  
  
n=x+1
while True:
  if a(n):
    pint(n)
    quit()
  n+=1

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

x=int(readline())
def a(n):
  for i in range(2, int(n ** 0.5 + 1)):
    if n % i == 0:
      return False
  return True
  

while True:
  if a(x):
    print(x)
    quit()
  x+=1
k,x=map(int,input().split())
if 500*k=>x:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

k,x=map(int,input().split())
if 500*k>=x:
  print("Yes")
else:
  print("No")
mod = 10**9 + 7
x,y = map(int,input().split())
dp = [[0]*(y+3) for _ in range(x+3)]
dp[0][0] = 1

for i in range(x+1):
    for j in range(y+1):
        if dp[i][j] >= mod:
            dp[i][j] %= mod
        if dp[i][j] == 0:
            continue
        else:
            if i+2 <= x+1 and j+1 <= y+1:
                dp[i+2][j+1] += dp[i][j]
            if i+1 <= x+1 and j+2 <= y+1:
                dp[i+1][j+2] += dp[i][j]
print(dp[x][y])

### FIXED CODE ###

x,y = map(int,input().split())
mod = 10**9 + 7
if (x+y)%3 != 0:
    print(0)
    exit()
n = (x+y)//3
a = (2 * x - y) // 3
b = (2 * y - x) // 3
if a == 0 or b == 0:
    print(1)
    exit()
if a < 0 or b < 0:
    print(0)
    exit()
MAX = 700000
fac = [1,1] + [0] * MAX     #累積積
finv = [1,1] + [0] * MAX    #modにおける逆元
inv = [0,1] + [0] * MAX     #invの累積積
for i in range(2,MAX):
    fac[i] = fac[i-1] * i % mod
    inv[i] = -inv[mod%i] * (mod//i)%mod
    finv[i] = finv[i-1] * inv[i]%mod


def nCr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n] * (finv[r] * finv[n-r]%mod)%mod

print(nCr(n,a))
int(input())

### FIXED CODE ###

print('bwuisnt'[sum(map(int,input().split()))<22::2])
import heapq

X,Y,Z,K = map(int, input().split())
A = [int(x) for x in  input().split()]
B = [int(x) for x in  input().split()]
C = [int(x) for x in  input().split()]

A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)

h = []

heapq.heappush(h, (A[0]+B[0]+C[0], 0,0,0))

result = []
used = set()

for _ in range(K):
    value, i,j,k = heapq.heappop(h)
    result.append(value)
    if i < X-1 and (i+1,j,k) not in used:
        heapq.heappush(h, (A[i+1]+B[j]+C[k],i,j,k))
		used.add((i+1,j,k))
    if j < Y-1 and (i,j+1,k) not in used:
        heapq.heappush(h, (A[i]+B[j+1]+C[k],i,j+1,k))
		used.add((i,j+1,k))
    if k < Z-1 and (i,j,k+1) not in used:
        heapq.heappush(h, (A[i]+B[j]+C[k+1],i,j,k+1))
		used.add((i,j,k+1))
        
for v in result:
    print(v)

### FIXED CODE ###

import heapq

X,Y,Z,K = map(int, input().split())
A = [int(x) for x in  input().split()]
B = [int(x) for x in  input().split()]
C = [int(x) for x in  input().split()]

A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)

h = []

heapq.heappush(h, (-A[0]-B[0]-C[0], 0,0,0))

result = []
used = set()

for _ in range(K):
    value, i,j,k = heapq.heappop(h)
    result.append(-value)
    if i < X-1 and (i+1,j,k) not in used:
        heapq.heappush(h, (-A[i+1]-B[j]-C[k],i+1,j,k))
        used.add((i+1,j,k))
    if j < Y-1 and (i,j+1,k) not in used:
        heapq.heappush(h, (-A[i]-B[j+1]-C[k],i,j+1,k))
        used.add((i,j+1,k))
    if k < Z-1 and (i,j,k+1) not in used:
        heapq.heappush(h, (-A[i]-B[j]-C[k+1],i,j,k+1))
        used.add((i,j,k+1))
        
for v in result:
    print(v)
N,D=map(int,input().split())
people=N/(2D+1)
if people%2==O:
    print(int(people))
else:
    print(int(people)+1)


### FIXED CODE ###

N,D=map(int,input().split())
people=N/(2*D+1)
if N % (2*D+1) == 0:
    print(int(people))
else:
    print(int(people)+1)
def main():
  X = int(input())

  i = 0
  while True:
    tmp = X + i**5
    tmp5 = tmp**0.2
    if abs(tmp5 - int(tmp5)) < 1e-8:
      print("{} {}".format(i, int(tmp5)))
      return 0

    tmp = X - i**5
    tmp5 = tmp**0.2
    if abs(tmp5 - int(tmp5)) < 1e-8:
      print("{} {}".format(i, int(-tmp5)))
      return 0
    i += 1
    
if __name__ == '__main__':
  main()


### FIXED CODE ###

def main():
    X = int(input())

    a = -1
    
    while True:
        b1 = 0
        b2 = 0
        while b1 < a:
            
            if (X/(a-b1)).is_integer():
                if int(X/(a-b1)) == a**4 + b1*(a**3) + (a**2)*(b1**2) + a*(b1**3) + b1**4:
                    print("{} {}\n".format(a, b1))
                    return 0

            if (X/(a-b2)).is_integer():
                if int(X/(a-b2)) == a**4 + b2*(a**3) + (a**2)*(b2**2) + a*(b2**3) + b2**4:
                    print("{} {}\n".format(a, b2))
                    return 0

            b1 += 1
            b2 -= 1
            
        a += 1


if __name__ == "__main__":
    main()
N,W=map(int,input().split())
w=[]
v=[]
for i in range(n):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
dp=[[10**22]*(N*(10**3)+1) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    for j in range(N*(10**3)+1):
        if j>=v[i]:
            dp[i][j]=min(dp[i-1][j-v[i]]+w[i],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(N*(10**3),-1,-1):
    if dp[N][i]<=W:
        print(i)
        break


### FIXED CODE ###

N,W=map(int,input().split())
taple=[]
for i in range(N):
    w,v=map(int,input().split())
    taple.append((w,v))
dp=[[10**22]*(N*(10**3)+1) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    w,v=taple[i-1]
    for j in range(N*(10**3)+1):
        if j>=v:
            dp[i][j]=min(dp[i-1][j-v]+w,dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(N*(10**3),-1,-1):
    if dp[N][i]<=W:
        print(i)
        break
x=int(input())
y=int(input())
print(x*y)

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b,(a+b)*2)
N,A,B,C,D=map(int,input().split())
S=input()

if C<D:
    if "##" not in S[A:C-1] or "##" not in S[B:D-1]:
        print("Yes")
    else:
        print("No")
elif C>D
    if "##" not in S and "..." not in S[B-2:D+1]:
        print("Yes")
    else:
        print("No")
else:
    print("Yes")


### FIXED CODE ###

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

if "##" in S[A:C-1] or "##" in S[B:D-1]:
    print("No")
    exit()
elif C>D and "..." not in S[B-2:D+1]:
    print("No")
else:
    print("Yes")
import sys
G = list(map(int, input().split()))
total = G[0] + G[1]
if total % 3 != 0:
  print(0)
  sys.exit(0)

total //= 3
dis = G[0] - total

mod = 10 ** 9 + 7
fact = [1]
fact_inv = [1]
for i in range(10**6+4):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))

def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

print(comb_mod(total, min(G)-total))


### FIXED CODE ###

import sys
G = list(map(int, input().split()))
total = G[0] + G[1]
if total % 3 != 0:
  print(0)
  sys.exit(0)

total //= 3
dis = G[0] - total

MOD = 10 ** 9 + 7
def inv_mod(a, p=MOD):
    def inv_mod_sub(a, p):
        if a == 1:
            return 1, 0
        else:
            d, r = p//a, p%a
            x, y = inv_mod_sub(r, a)
            return y-d*x, x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n, k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD
f_mod=[1]*(10**6)
f_mod_inverse=[1]*(10**6)
for i in range(1,10**6):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD

print(comb_mod(total, dis))