Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
import math
readline = sys.stdin.readline

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

q_array = []

score_needed = 0

for i in range(N):
    b, l, u = map(int, readline().split())
    q_array.append([b, l, u, b * l + (X - b) * u])
    score_needed += b * l

q_array = sorted(q_array, key=lambda x: -x[3])

ans = 0
# print(q_array)
for i in range(N):
    if q_array[i][3] <= score_needed:
        ans += X
        score_needed -= q_array[i][3]
        if score_needed == 0:
            break
    else:
        study_min = X
        # print(score_needed)
        for j in range(i, N):
            b, l, u, s = q_array[j]
            if score_needed > s:
                break
            yobun = s - score_needed
            if score_needed <= b * l:
                study_min = min(study_min, math.ceil(score_needed / l))
            else:
                study_min = min(study_min, b + math.ceil(
                    (score_needed - b * l) / u))
            for k in range(i):
                b, l, u, s = q_array[k]
                needed = s - yobun
                if score_needed <= b * l:
                    study_min = min(study_min, math.ceil(needed / l))
                else:
                    study_min = min(study_min, b + math.ceil(
                        (needed - b * l) / u))
        ans += study_min
        break
print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.readline

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

q_array = []
s_array = []

score_needed = 0

for i in range(N):
    b, l, u = map(int, readline().split())
    q_array.append([b, l, u, b * l + (X - b) * u])
    s_array.append(b * l + (X - b) * u)
    score_needed += b * l

q_array = sorted(q_array, key=lambda x: -x[3])
s_array = sorted(s_array, key=lambda x: -x)
sum_array = []
ss = 0
for s in s_array:
    ss += s
    sum_array.append(ss)
ans_min = 0
ans_max = N * X
if score_needed == 0:
    print(0)
    exit()
while ans_max - ans_min > 1:
    ans = (ans_min + ans_max) // 2
    use_all = ans // X
    use_part = ans % X
    # print(use_all, use_part)
    score_get_max = 0
    score_tmp = 0
    if use_part == 0:
        score_get_max = sum_array[use_all - 1]
    else:
        score_get_max = 0
        score_tmp = 0
        for q in q_array:
            b, l, u, s = q
            score_tmp = 0
            if use_part <= b:
                score_tmp = use_part * l
            else:
                score_tmp = (b * l + (use_part - b) * u)
            if use_all > 0:
                if s_array[use_all - 1] <= s:
                    score_tmp += (sum_array[use_all] - s)
                else:
                    score_tmp += sum_array[use_all - 1]
            score_get_max = max(score_get_max, score_tmp)
    # print(ans, score_get_max)
    if score_get_max >= score_needed:
        ans_max = ans
    else:
        ans_min = ans

print(ans_max)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
Binary Search
n ????????´??°???????????°??? S ??¨???q ????????°????????´??°???????????°??? T ??????????????????
T ?????????????????´??°????????§ S ?????????????????????????????° C ???????????????????????°????????????????????????????????????
"""
def bsrch(l, a):
    """ ????????????????????? """
    c = int(len(l) / 2)
    if l[c] == a:
        return True
    else:
        if c > 0:
            if l[c] > a:
                return bsrch(l[:c], a)
            elif l[c] < a:
                return bsrch(l[c:], a)
    return False

def main():
    """ ????????? """
    n = int(input())
    S = list(map(int,input().split()))
    q = int(input())
    T = list(map(int,input().split()))

    cnt = {}

    for j in range(q):
       x = bsrch(S, T[j])
       if x == True:
           cnt[T[j]] = 1
    print(len(cnt))

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
Binary Search
n ????????´??°???????????°??? S ??¨???q ????????°????????´??°???????????°??? T ??????????????????
T ?????????????????´??°????????§ S ?????????????????????????????° C ???????????????????????°????????????????????????????????????
"""
def bsrch(l, s, e, a):
    """ ????????????????????? """
    c = int((e - s) / 2) + s if e - s > 1 else s
    x = l[c]
#    print(l[s:e])
#    print("s:{} e:{} c:{} a:{}".format(s,e,c,a))
    if x == a:
        return True
    else:
        if c > s:
            if x < a:
                return bsrch(l, c, e, a)
            elif x > a:
                return bsrch(l, s, c, a)
    return False

def main():
    """ ????????? """
    n = int(input())
    S = list(map(int,input().split()))
    q = int(input())
    T = list(map(int,input().split()))

    cnt = {}
    for j in range(q):
       x = bsrch(S, 0, n, T[j])
       if x == True:
           cnt[T[j]] = 1
    print(len(cnt))

if __name__ == '__main__':
    main()
### BUGGY CODE ###

#https://atcoder.jp/contests/abc153/tasks/abc153_c

n,k=map(int,input().split())
h=list(map(int,input().split()))
for _ in range(k):
    h[h.index(max(h))]=0
sum=0
for l in h:
    sum+=l
print(sum)

### FIXED CODE ###

#https://atcoder.jp/contests/abc153/tasks/abc153_c

n,k=map(int,input().split())
h=list(map(int,input().split()))
h.sort()
sum=0
for i in range(n-k):
    sum+=h[i]
print(sum)
### BUGGY CODE ###

def main():
    from sys import stdin
    input = stdin.readline
    import numpy as np
    h, w, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    ab_d = {(a, b) for a, b in ab}

    ans = [set() for _ in range(10)]
    ans[0] = 0
    for a, b in ab:
        temp = np.full((5, 5), -1, dtype=np.int8)
        for i in range(max(0, 3-a), min(5, h-a+3)):
            for j in range(max(0, 3-b), min(5, w-b+3)):
                if (a+i-2, b+j-2) in ab_d:
                    temp[i, j] = 1
                else:
                    temp[i, j] = 0
        # print(temp)
        yoko_0 = max(3-b, 0)
        yoko_1 = min(w-b+3, 5)
        tate_0 = max(3-a, 0)
        tate_1 = min(h-a+3, 5)
        new_temp = temp[tate_0:tate_1, yoko_0:yoko_1]
        for i in range(tate_1-tate_0-2):
            for j in range(yoko_1-yoko_0-2):
                ans[np.sum(new_temp[i:i+3, j:j+3])
                    ].add((a+i+tate_0, b+j+yoko_0))

    for i in range(9):
        ans[i+1] = len(ans[i+1])

    print((h-2)*(w-2)-sum(ans))
    for i in ans[1:]:
        print(i)


main()


### FIXED CODE ###

h,w,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*n]
ab_d={a*(10**9)+b-1 for a,b in ab}

ans=[set() for _ in range(9)]
for a,b in ab:
    temp=[None for _ in [0]*25]
    for i in range(5):
        for j in range(5):
            if 0<a+i-2<=h and 0<b+j-2<=w:
                if (a+i-2)*(10**9)+b+j-3 in ab_d:
                    temp[i*5+j]=1
                else:
                    temp[i*5+j]=0
    for i in range(3):
        for j in range(3):
            cnt=[temp[(i+k)*5+j+l] for k in range(3) for l in range(3)]
            if None not in cnt:
                ans[sum(cnt)-1].add((a+i-2)*(10**9)+b+j-3)
                
for i in range(9):
    ans[i]=len(ans[i])

print((h-2)*(w-2)-sum(ans))
for i in ans:
    print(i)
### BUGGY CODE ###

import queue
height,width=map(int,input().split())

graph=[input() for _ in range(height)]

diff=[[0,-1],[0,1],[-1,0],[1,0]]
max_step=[]
for h in range(height):
    for w in range(width):
        if graph[h][w]=='#':
            continue

        route = [[-1]*width for _ in range(height)]

        # start x,y,経路数
        q = queue.Queue()
        q.put([w,h,0])

        while not q.empty():
            nx,ny,nn = q.get()
            route[ny][nx] = nn

            for dx,dy in diff:
                x = nx+dx
                y = ny+dy
                if   width<=x \
                  or height<=y \
                  or x < 0 \
                  or y < 0 \
                  or graph[y][x]=='#' \
                  or route[y][x]!=-1:
                    continue
                q.put([x, y, nn+1])
        
        max_step.append(max(max(step) for step in route))
        
print(max(max_step))

### FIXED CODE ###

import queue
height,width=map(int,input().split())

graph=[input() for _ in range(height)]

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
max_step=[]
for h in range(height):
    for w in range(width):
        if graph[h][w]=='#':
            continue

        route = [[-1]*width for _ in range(height)]
        route[h][w] = 0

        # start x,y,経路数
        q = queue.Queue()
        q.put([w,h,0])

        while not q.empty():
            nx,ny,nn = q.get()

            for dx,dy in zip(dxs, dys):
                x = nx+dx
                y = ny+dy
                if   width<=x \
                  or height<=y \
                  or x < 0 \
                  or y < 0 \
                  or graph[y][x]=='#' \
                  or route[y][x]!=-1:
                    continue
                route[y][x] = nn + 1
                q.put([x, y, nn+1])
        
        max_step.append(max(max(step) for step in route))
        
print(max(max_step))
### BUGGY CODE ###

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

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = pow(10,9) + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2,n + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

print(pow(2,n,p) - cmb(n, a, p) -cmb(n, b, p) -1)


### FIXED CODE ###

n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
 
 
def cmb(n, r, mod):
    r = min(r, n - r)
    x = 1
    y = 1
    for i in range(r):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    y = pow(y, mod-2, mod)
    return x * y % mod
 

ans = pow(2, n, mod) - 1 - cmb(n, a, mod) - cmb(n, b, mod)
while ans < 0:
    ans += mod
print(ans)
### BUGGY CODE ###

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

ans = "YES"
for t in T:
    if t not in d: 
        ans = "NO"
        break
    d.pop(d.index(t))
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))
d = Counter(sorted(d))
cnt = 0
for i in range(m):
    if t[i] in d and d[t[i]] > 0:
        d[t[i]] -= 1
        cnt += 1
    else: break
print("YES" if cnt == m else "NO")
### BUGGY CODE ###

n,mw=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
dp=[[0 for _ in range(mw+1)]for _ in range(n+1)]
for i in range(n):
    w,v=l[i]
    for j in range(mw):
        dp[i+1][j]=max(dp[i+1][j],dp[i][j])
        if j+w<=mw:
            dp[i+1][j+w]=max(dp[i+1][j+w],dp[i][j]+v)
print(max(dp[-1]))

### FIXED CODE ###

n,mw=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
dp=[[0 for _ in range(mw+1)]for _ in range(n+1)]
for i in range(n):
    w,v=l[i]
    for j in range(mw):
        dp[i+1][j]=max(dp[i+1][j],dp[i][j])
        if j+w<=mw:
            dp[i+1][j+w]=max(dp[i+1][j+w],dp[i][j]+v)
print(max(dp[-1]))
### BUGGY CODE ###

import sys

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

for i in reversed(range(y//10000 + 1)):
	n -= i
	y -= 10000 * i
	for j in reversed(range(y//5000 + 1)):
		n -= j
		y -= 5000 * j
		for k in reversed(range(y//1000 + 1)):
			n -= k
			y -= 1000 * k
			if y == 0 and n == 0:
				print(i,j,k)
				sys.exit()
			n += k
			y += 1000 * k
		n += j
		y += 5000 * j
	n += i
	y += 10000 * i

print("-1 -1 -1")


### FIXED CODE ###

import sys

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

if y // 10000 > n:
	print("-1 -1 -1")
	sys.exit()

for i in reversed(range(y//10000 + 1)):
	n -= i
	y -= 10000 * i
	if 10000 * i + 5000 * (n-i) < y:
		break
	for j in reversed(range(y//5000 + 1)):
		n -= j
		y -= 5000 * j
		for k in reversed(range(y//1000 + 1)):
			n -= k
			y -= 1000 * k
			if y == 0 and n == 0:
				print(i,j,k)
				sys.exit()
			else:
				n += k
				y += 1000 * k
				break
		n += j
		y += 5000 * j
	n += i
	y += 10000 * i

print("-1 -1 -1")
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
n = int(input())
a = list(map(int, input().split()))
from fractions import gcd
from functools import reduce
def lcm(x,y):
  return (x*y)//gcd(x,y)
l = reduce(lcm, a)
mod = 10**9+7
ans = 0
for i in range(n):
  ans += l // a[i]
  ans %= mod
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
from fractions import gcd
from functools import reduce
def lcm(x,y):
  return (x*y)//gcd(x,y)
mod = 10**9+7
l = reduce(lcm, a) % mod
ans = 0
for i in range(n):
  ans += l * pow(a[i], mod - 2, mod)
  ans %= mod
print(ans)
### BUGGY CODE ###

cnt = 0
n = 357
l = int(input())+1
while n<l:
    #print(n)
    s = str(n)

    ok = False
    for i in "0124689":
        if i in s:
            ok = True
            break

    if ok:
        #print(s)
        if s[0] == '1':
            n += 2*(10**(len(s)-1))
        elif s[0] == '4' or s[0] == '6':
            n += 10**(len(s)-1)
        else:
            n+=2
        continue
        
    if '3' in s and '5' in s and '7' in s:
        #print(s)
        cnt += 1
        
    n+=2
print(cnt)


### FIXED CODE ###

n = int(input())
def count(s):
    if len(s) == len(str(n)):
        if ('3' in s) and ('5' in s) and ('7' in s) and (int(s) <= n) and not ('0' in str(int(s))):
            #print(s)
            return 1
        else:
            return 0
    ret = 0
    for i in "0357":
        ret += count(s+i)
    return ret

print(count(""))
### BUGGY CODE ###

N = int(input())
S = list(input())
f=0
i_c = j_c = k_c =1
ijk = list()
for i in range(N):
    for j in range(N):
        for k in range(N):
            if(k_c>j_c and j_c>i_c): 
                if(j_c-i_c==k_c-j_c):
                    pass
                else:
                    ijk.append([i,j,k])
            k_c+=1
        j_c+=1
        k_c = 1
    i_c+=1
    j_c = 1



for i in range(len(ijk)):
    if(S[ijk[i][0]]!= S[ijk[i][1]] and
       S[ijk[i][0]]!= S[ijk[i][2]] and
       S[ijk[i][1]]!= S[ijk[i][2]]):
       f+=1
print(f)

### FIXED CODE ###

n=int(input())
s=input()
r=g=b=0
for i in s:
  if i=="R":r+=1
  elif i=="G":g+=1
  else:b+=1

ans=r*g*b
for i in range(n):
  for j in range(i+1,n):
    k_ = j+(j-i)
    if(k_ >=n):
      break
    ans -= int(s[i]!= s[j] and s[i] != s[k_] and s[j] != s[k_])

print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline

from collections import deque
import numpy as np

def myinput():
    return map(int,readline().split())

h,w = myinput()
field = [ list(input()) for _ in range(h) ]

d = [ [float("inf")]*w for _ in range(h) ]
q = deque()

for j in range(h):
    for i in range(w):
        a = field[j][i]
        if a=="#":
            q.append([j,i])
            d[j][i] = 0
        else:
            pass

def bfs(d):
    while q:
        y,x = q.popleft()
        for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
            ny = y + j
            nx = x + i
            if ny==-1 or nx==-1 or ny==h or nx==w:
                pass
            elif field[ny][nx]=="#":
                pass
            elif d[ny][nx]!=float("inf"):
                pass
            else:
                field[ny][nx] = "#"
                d[ny][nx] = d[y][x] + 1
                q.append([ny,nx])
    return d

d2 = bfs(d)
d3 = np.array(d2)
ans = np.max(d3)
print(ans)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
field = [ list(input()) for _ in range(h) ]

visited = [ [0]*w for _ in range(h) ]
q = deque()

for j in range(h):
    for i in range(w):
        a = field[j][i]
        if a=="#":
            q.append([j,i,0])
            visited[j][i] = 1
        else:
            pass

m = 0
while q:
    y,x,d = q.popleft()
    for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
        ny = y + j
        nx = x + i
        if ny==-1 or nx==-1 or ny==h or nx==w:
            pass
        elif visited[ny][nx]==0:
            visited[ny][nx] = 1
            q.append([ny,nx,d+1])
            m = max(m,d+1)   
print(m)
### BUGGY CODE ###

L,R=map(int,input().split())

A=[]

for i in range(R-L+1):
    for j in range(R-i-L):
        A.append((i+L)*(j+i+L+1)%2019)
print(min(A))

### FIXED CODE ###

import itertools
L,R=map(int,input().split())

A=[]
D=[]

if R-L+1<2019:
    for i in range(R-L+1):
        A.append((i+L)%2019)

    if A.count(1)>=2:
        B=set(A)
        B.add(1)
    else:
        B=set(A)

    C=list(itertools.combinations(B,2))
    for j in range(len(C)):
        D.append(C[j][0]*C[j][1]%2019)
    E=sorted(D)
    print(E[0])
else:
    print(0)
### BUGGY CODE ###

from collections import defaultdict as dd

N, M = map(int, input().split())
MOD = 10**9 + 7
s = list(map(int, input().split()))
t = list(map(int, input().split()))

dp = [[0 for i in range(M+1)] for j in range(N+1)]
for j in range(M):
    dp[1][j + 1] = dp[1][j] + 1 if s[0] == t[j] else dp[1][j]

for i in range(N):
    dp[i + 1][1] = dp[i][1] + 1 if t[0] == s[i] else dp[i][1]

if N > 1 and M > 1:
    for i in range(1, N):
        for j in range(1, M):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] + 1
            else:
                dp[i + 1][j + 1] = dp[i][j+1] + dp[i+1][j] - dp[i][j]
    
print((dp[N][M] + 1)%MOD)


### FIXED CODE ###

N, M = map(int, input().split())
MOD = 10**9 + 7
s = list(map(int, input().split()))
t = list(map(int, input().split()))

dp = [[0 for i in range(M+1)] for j in range(N+1)]
for j in range(M):
    dp[1][j + 1] = dp[1][j] + 1 if s[0] == t[j] else dp[1][j]

for i in range(N):
    dp[i + 1][1] = dp[i][1] + 1 if t[0] == s[i] else dp[i][1]

for i in range(1, N):
    for j in range(1, M):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] + 1)%MOD
        else:
            dp[i + 1][j + 1] = (dp[i][j+1] + dp[i+1][j] - dp[i][j])%MOD
    
print((dp[N][M] + 1)%MOD)
### BUGGY CODE ###

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

K = {}
for row in A:
    if row in K:
        K[row] += 1
    else:
        K[row] = 1

# 辞書Kに関して全探索
D = {}
C = {}
for row in A:
    ans = 0
    if row not in D:
        for i in K:
            tmp = 0
            if i == row:
                tmp = K[i]-1
            else:
                tmp = K[i]
            if tmp not in C:
                ans += tmp * ( tmp-1 ) / 2
            else:
                ans += C[tmp]
        D[row] = int(ans)
        print(D[row])
    else:
        print(D[row])


### FIXED CODE ###

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

K = {}
for row in A:
  if row in K:
    K[row] += 1
  else:
    K[row] = 1
        
# 最大数を計算
max = 0
for i in K:
  max += int(K[i]*(K[i]-1)/2)

# 辞書Kに関して全探索
for i in A:
  print(max - int(K[i]*(K[i]-1)/2) + int((K[i]-1)*(K[i]-2)/2) )
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]
ans[ch-1][cw-1]=0
count=0

def bfs(ans):
  qu = deque([])
  qu.append((cw-1,ch-1))
  while qu:
    x,y=qu.popleft()

    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        if (x==i and y==j):
          continue
        if 0<=i<w and 0<=j<h:
          if maze[j][i]=="." and (ans[j][i]>ans[y][x] or ans[j][i]==-1):
            if (x==i and y==j+1) or (x==i+1 and y==j) or (x==i-1 and y==j) or (x==i and y==j-1):
              qu.appendleft((i,j))
              ans[j][i] = ans[y][x]
            elif ans[j][i]>ans[y][x]+1 or ans[j][i]==-1:
              ans[j][i]=(ans[y][x]+1)
              qu.appendleft((i,j))

bfs(ans)
print(ans[dh-1][dw-1])
#for i in ans:
#  print(*i)
  



### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

dx=[0,1,0,-1]
dy=[1,0,-1,0]

ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    count=0
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
        if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
          qu.appendleft([x+dx[i],y+dy[i]])
          ans[y+dy[i]][x+dx[i]] = ans[y][x]
          count+=1
    if count!=4:
      for i in range(x-2,x+3):
        for j in range(y-2,y+3):
          if 0<=i<w and 0<=j<h:
            if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
              ans[j][i]=(ans[y][x]+1)
              qu.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])
### BUGGY CODE ###

line = input()
data = line.split(" ")
shoplist = [] #店のデータリスト
for i in range(int(data[0])):
    shop = input()
    shopdata = shop.split(" ")
    shop_int = []
    for j in range(len(shopdata)):
        shop_int.append(int(shopdata[j]))
    shoplist.append(shop_int)

payment = 0 #支払い金額
wantdrink = int(data[1]) #ほしい飲み物の数
while wantdrink > 0 :
    pricelist = []  #金額のみのデータリスト
    for i in range(len(shoplist)):
        pricelist.append(shoplist[i][0])
    pricemin = min(pricelist[i] for i in range(len(pricelist)))
    min_index = pricelist.index(pricemin)
    restwater = shoplist[min_index][1]
    while restwater > 0:
        payment += pricemin
        restwater -= 1
        wantdrink -= 1
        if wantdrink == 0:
            break
    del shoplist[min_index]
print(payment)

### FIXED CODE ###

# coding: utf-8

data = input().split()
shoplist = []
for i in range(int(data[0])):
    shopdata = list(map(int, input().split()))
    shoplist.append(shopdata)
shoplist.sort()

payment = 0
wantdrink = int(data[1])
while wantdrink > 0 :
    restdrink = shoplist[0][1]
    if restdrink >= wantdrink:
        payment += wantdrink * shoplist[0][0]
        break
    else:
        payment += restdrink * shoplist[0][0]
        wantdrink -= restdrink
        del shoplist[0]
print(payment)
### BUGGY CODE ###

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

b=[0]*N
for a in A:
    b[a-1]+=1
    
c=[0]*N
tmp=b
for i in range(N):
    c[i]+=tmp[i]*(tmp[i]-1)//2
    
for a in A:
    b[a-1]-=1
    print(sum(c)-c[a-1]+b[a-1]*(b[a-1]-1)//2)
    b[a-1]+=1
    

### FIXED CODE ###

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

b=[0]*N
for a in A:
    b[a-1]+=1
    
c=[0]*N
tmp=b
for i in range(N):
    c[i]+=tmp[i]*(tmp[i]-1)//2
sum_c=sum(c)

for a in A:
    b[a-1]-=1
    print(sum_c-c[a-1]+b[a-1]*(b[a-1]-1)//2)
    b[a-1]+=1
### BUGGY CODE ###

n =int(input())
temp = list(map(int, input().split()))
a = 1
for i in range(n):
  a=a*temp[i]
if a>10**18:
  print(-1)
else:
  print(a)

### FIXED CODE ###

n =int(input())
temp = list(map(int, input().split()))
temp = sorted(temp)
a = 1
for i in range(n):
  a=a*temp[i]
  if a>10**18:
    print(-1)
    break
else:
  print(a)
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1,N):
    if N % i == 0:
        temp = N // i - 1
        d,m = divmod(N,temp)
        if d != m:
            break
        else:
            ans += temp
print(ans)

### FIXED CODE ###

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)
    return divisors

N = int(input())
divisors = make_divisors(N)
ans = 0
divisors.sort(reverse=True)
for x in divisors:
    if x > 1:
        temp = x - 1
        d,m = divmod(N,temp)
        if d != m:
            break
        else:
            ans += temp
print(ans)