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

R, G, B, N = list(map(int, input().split()))

count = 0

len_r = N // R + 2
len_g = N // G + 2
for ix in range(len_r):
    for iy in range(len_g):
        sum = N - (R * ix + G * iy)
        if sum >= 0 and sum % B == 0:
            count += 1
        if R * ix + G + iy > N:
            break

print(count)

### FIXED CODE ###

R, G, B, N = list(map(int, input().split()))

count = 0

len_r = N // R + 2
for ix in range(len_r):
    len_g = (N - (R * ix)) // G + 2
    for iy in range(len_g):
        t = N - (R * ix + G * iy)
        if t >= 0 and t % B == 0:
            count += 1
print(count)
### BUGGY CODE ###

n, k = map(int, input().split())
ans = n
if k == 1 or n == 0:
    print(0)
    exit()
while True:
    if ans < abs(n-k):
        break
    else:
        n = abs(n-k)
        ans = n
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
print(min(n%k, abs((n // k + 1) * k - n)))
### BUGGY CODE ###

import heapq
n = int(input())
a_list = []

for i in range(n):
    a = int(input())
    if a in a_list:
        a_list.remove(a)
    else:
        heapq.heappush(a_list, a)

print(len(a_list))


### FIXED CODE ###

n = int(input())
d = dict()
for i in range(n):
    a = int(input())
    if a in d:
        if d[a] == 0:
            d[a] = 1
        else:
            d[a] = 0
    else:
        d[a] = 1

print(sum(d.values()))
### BUGGY CODE ###

n,p = map(int,input().split())
s = input()
num = 0
s1 = [0]*(n+1)
ans = 0
if p == 2 or p == 5:
	for i in range(len(s)):
		if int(s[i])%p == 0:
			ans += i+1	
	print(ans)
	exit()
ans = 0
arr = [0]*p
s = s[::-1]
z = 1
for i in range(n):
	s1[i+1] = s1[i] + int(s[i])*z
	z *=10 %p
	s1[i+1] %=p
	arr[s1[i]] += 1
arr[s1[n]]+=1
#print(s1)
for i in range(p):
	ans += arr[i] * (arr[i] - 1) // 2
print(ans)


### FIXED CODE ###

def main():
	N,P = map(int,input().split())
	S = [int(s) for s in list(input().strip())][::-1]
	num = 0
	ans = 0
	if P == 2 or P == 5:
		for i in range(N):
			if S[i]%P == 0:
				ans += N-i
		print(ans)
		return
	L = [0]*P
	L[0]=1
	t = 0
	s = 1
	for z in S:
		t = (z*s+t)%P	
		L[t]+=1
		s=s*10%P
	for l in L:
		ans += l * (l - 1) // 2
	print(ans)

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

from heapq import heappush,heappop
import queue
import re
import math
import functools
import numpy as np

def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

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


N = int_raw()
As =[]
for _ in range(N):
    As.append(int_raw())
SUM = sum(As)

DIV = 998244353

ALL = 1
for _ in range(N):
    ALL = (ALL*3)%DIV

def main():
    dp1 = np.zeros((N+1, SUM+1), dtype=np.int)
    dp3 = np.zeros((N+1, SUM+1), dtype=np.int)
    dp1[0][0]=1
    dp3[0][0]=1
    
    for n in range(N):
        a = As[n]
        for s in range(SUM+1):
            dp1[n+1][s]=dp1[n][s]
            dp3[n+1][s]=(2*dp3[n][s])%DIV
            if s>=a:
                dp1[n+1][s]= (dp1[n+1][s]+ dp1[n][s-a])%DIV
                dp3[n+1][s]= (dp3[n+1][s]+ dp3[n][s-a])%DIV
    S3 = (sum(dp3[N][(SUM+1)//2:])*3)%DIV
    S1 = (dp1[N][(SUM)//2]*3)%DIV if SUM%2==0 else 0
    return (ALL - S3 + S1 + DIV) % DIV

print(main())


### FIXED CODE ###

from heapq import heappush,heappop
import queue
import re
import math
import functools


def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

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


N = int_raw()
As =[]
for _ in range(N):
    As.append(int_raw())
SUM = sum(As)

DIV = 998244353

ALL = 1
for _ in range(N):
    ALL = (ALL*3)%DIV

def main():
    dp1 = [0]*(SUM+1)
    dp3 = [0]*(SUM+1)
    dp1[0]=1
    dp3[0]=1
    
    for n in range(N):
        a = As[n]
        dp1 = [(dp1[s]+(dp1[s-a] if s>=a else 0))%DIV for s in range(SUM+1)]
        dp3 = [(dp3[s]*2 + (dp3[s-a] if s>=a else 0))%DIV for s in range(SUM+1)]

    S3 = (sum(dp3[(SUM+1)//2:])*3)%DIV
    S1 = (dp1[(SUM)//2]*3)%DIV if SUM%2==0 else 0
    return (ALL - S3 + S1 + DIV) % DIV

print(main())
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C


if __name__ == '__main__':
    spot_count = int(input())
    mod_spots = [0] + list(map(int, input().split())) + [0]

    for i in range(spot_count):
        tmp = mod_spots[i + 1]

        if mod_spots[i] <= mod_spots[i + 2]:
            mod_spots[i + 1] = mod_spots[i]
        elif (mod_spots[i] > 0) and mod_spots[i + 2] > 0:
            mod_spots[i + 1] = 0
        else:
            mod_spots[i + 1] = mod_spots[i]

        cost = {j: abs(mod_spots[j + 1] - mod_spots[j]) for j in range(spot_count + 1)}
        mod_spots[i + 1] = tmp
        print(sum(cost.values()))


### FIXED CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    spot_count = int(input())
    spots = [0] + list(map(int, input().split())) + [0]

    # See:
    # https://www.youtube.com/watch?v=WFg2yJGZ2Cw
    # https://img.atcoder.jp/arc093/editorial.pdf
    total_distance = 0
    total_cost = 0

    for i in range(spot_count + 1):
        total_distance += abs(spots[i + 1] - spots[i])

    for j in range(1, spot_count + 1):
        shortcut_cost = (abs(spots[j - 1] - spots[j]) + abs(spots[j] - spots[j + 1]))
        total_cost = total_distance + abs(spots[j - 1] - spots[j + 1]) - shortcut_cost
        print(total_cost)
### BUGGY CODE ###

n = int(input())
lst = list(map(int,input().split()))
mod = 10 ** 9 + 7

ans = 0

for i in range(n-1):
    tmp = lst[i] * sum(lst[i+1:])
    ans = (ans + tmp) % mod

print(ans)

### FIXED CODE ###

n = int(input())
lst = list(map(int,input().split()))
mod = 10 ** 9 + 7

ans = 0
S = sum(lst)

for i in range(n-1):
    S = S - lst[i]
    tmp = lst[i] * S
    ans = (ans + tmp) % mod

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

s=input()

counter=[0]*2019
counter[0]=1
for i in range(len(s)):
    num=int(s[i:])
    counter[num%2019]+=1

ans=0
for i in range(2019):
    c=counter[i]
    ans+=c*(c-1)/2
print(int(ans))





### FIXED CODE ###

s=input()

counter=[0]*2019
counter[0]=1
num=0
t=1
prefer=0
for i in reversed(s):
    num+=int(i)*t
    num%=2019
    t*=10
    t%=2019
    counter[num]+=1

ans=0
for i in range(2019):
    c=counter[i]
    ans+=c*(c-1)/2
print(int(ans))
### BUGGY CODE ###

import numpy as np
n = int(input())
s = np.array([''.join(sorted(input())) for _ in range(n)])
count = 0
for i in range(n):
    count += np.count_nonzero(s[i+1:] == s[i])
print(count)

### FIXED CODE ###

n = int(input())
count = 0
ls = dict([])
for i in range(n):
    si = ''.join(sorted(input()))
    if si in ls.keys():
        count += ls[si]
        ls[si] += 1
    else:
        ls[si] = 1
print(count)
### BUGGY CODE ###

NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])
An = sorted(tuple(map(int,input().split(' '))))
Fn = sorted(tuple(map(int,input().split(' '))),reverse=True)
An_s = sum(An)

min_time = -1 #middle_time = 0を含めるので -1
max_time = An[N-1] * Fn[0] #最大でかかる時間
x_cadidate = An[N-1] * Fn[0] #xの最小の候補
middle_time = -1
range_n = range(N)
#init_list = [0]*N
while True:
    # max_time+1は max_time=0まで求めるため
    middle_time = (min_time + max_time)//2 #二部探索ように 最大と最小の半分を考える この時 middle_time An[i] * Fn[i]の取りうる最大として考える 
    #new_list = init_list
    sum_ax = 0
    for i in range_n:
        ax = middle_time//Fn[i] # An[i] * Fn[i] = x < middle_time より
        if ax < An[i]:
            sum_ax += ax
        else:
            sum_ax += An[i]
    if  min_time+1 == max_time: #二部探索で全てを探索したら終了 
        break
    elif An_s - sum_ax <= K:
        if x_cadidate > middle_time:
            x_cadidate = middle_time 
        max_time = middle_time   #もう少し middle_timeを減らせる
    else:
        min_time = middle_time   #もう少し middle_timeは大きい

print(x_cadidate)

### FIXED CODE ###

NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])
An = sorted(list(map(int,input().split(' '))))
Fn = sorted(list(map(int,input().split(' '))),reverse=True)
An_s = sum(An)

min_time = -1 #middle_time = 0を含めるので -1
max_time = An[N-1] * Fn[0] #最大でかかる時間
x_cadidate = An[N-1] * Fn[0] #xの最小の候補
middle_time = -1
range_n = range(N)
#init_list = [0]*N
while True:
    # max_time+1は max_time=0まで求めるため
    middle_time = (min_time + max_time)//2 #二部探索ように 最大と最小の半分を考える この時 middle_time An[i] * Fn[i]の取りうる最大として考える 
    #new_list = init_list
    sum_ax = 0
    for i in range_n:
        ax = middle_time//Fn[i] # An[i] * Fn[i] = x < middle_time より
        if ax < An[i]:
            sum_ax += ax
        else:
            sum_ax += An[i]
    if  min_time+1 == max_time: #二部探索で全てを探索したら終了 
        break
    elif An_s - sum_ax <= K:
        if x_cadidate > middle_time:
            x_cadidate = middle_time 
        max_time = middle_time   #もう少し middle_timeを減らせる
    else:
        min_time = middle_time   #もう少し middle_timeは大きい

print(x_cadidate)
### BUGGY CODE ###

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

ans = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k == S: ans += 1
            if i+j+k > S: break
        if i+j > S: break
    if i > S: break

print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(K+1):
    for j in range(K+1):
        if 0 <= S-i-j <= K: ans+=1
        if S-i-j < 0: break
    if i > S: break

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

import sys
sys.setrecursionlimit(500000)

def dfs(v,d,p):
    memo[v] = d
    flag = False
    for i in graph[v]:
        if memo[i[0]] != -1:continue
        dfs(i[0],d+i[1],v)
    sub_tree[v].append(v)
    for j in graph[v]:
        if j[0] == p:continue
        sub_tree[v] += sub_tree[j[0]]
    if p == k-1:arr.append(sub_tree[v])
n = int(input())
graph = [[] for _ in range(n)]
memo = [-1]*n

for i in range(n-1):
    x,y,z = map(int,input().split())
    graph[x-1].append([y-1,z])
    graph[y-1].append([x-1,z])
q,k = map(int,input().split())
sub_tree = [[] for _ in range(n)]
arr = []
ary = [list(map(int,input().split())) for _ in range(q)]
dfs(k-1,0,0)
arr.pop()
a = [0,0]
for i in range(q):
    for j in range(len(arr)):
        if ary[i][0] in arr[j]:
            a[0] = j
        if ary[i][1] in arr[j]:
            a[1] = j
    if a[0] == a[1]:
        print(memo[ary[i][0]-1]+memo[ary[i][1]-1])
    else:
        print(memo[ary[i][0]-1]+memo[ary[i][1]-1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)

def dfs(v,d):
    memo[v] = d
    for i in graph[v]:
        if memo[i[0]] != -1:continue
        dfs(i[0],d+i[1])
        
n = int(input())
graph = [[] for _ in range(n)]
memo = [-1]*n
for i in range(n-1):
    x,y,z = map(int,input().split())
    graph[x-1].append([y-1,z])
    graph[y-1].append([x-1,z])
q,k = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(q)]
dfs(k-1,0)
print(*[memo[x-1]+memo[y-1] for x,y in ary],sep="\n")
### BUGGY CODE ###

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

for i in range(int(p**(1/n)+1),0,-1):
    if p%i!=0:
        continue
    if p%(pow(i,n))==0:
        print(i);exit()

### FIXED CODE ###

n, p = map(int, input().split())
di = {}
for i in range(2, int(p**0.5)+1):
    if p%i==0:
        tmp = 0
        while p%i==0:
            p //= i
            tmp += 1
        di[i] = tmp
    if p==1:
        break
else:
    di[p] = 1
ans = 1
for i, j in di.items():
    ans *= i**(j//n)
print(ans)
### BUGGY CODE ###

def calc_cost2(h, k):
    if (len(h) == 0):
        return 0

    cost = [None] * len(h)
    cost[0] = 0
    for i in range(1, len(h)):
        cost[i] = cost[i-1] + abs(h[i] - h[i-1])
        for s in range(max(0, i-k), i):
            cost[i] = min(cost[i], cost[s] + abs(h[i] - h[s]))

    return cost[len(h)-1]

if __name__ == "__main__":
    n, k = list(map(int, input().split(" ")))
    h = list(map(int, input().split(" ")))
    res = calc_cost2(h, k)
    print(res)

### FIXED CODE ###

def calc_cost2(h, k):
    n = len(h)
    if (n == 0):
        return 0

    cost = n * [None]
    cost[0] = 0
    for i in range(1, len(h)):
        cost[i] = min([cost[s] + abs(h[i] - h[s]) for s in range(max(0, i-k), i)])
        #cost[i] = min(map(lambda s: cost[s] + abs(h[i] - h[s]), range(max(0, i-k), i)))

    return cost[n-1]


if __name__ == "__main__":
    n, k = list(map(int, input().split(" ")))
    h = list(map(int, input().split(" ")))
    res = calc_cost2(h, k)
    print(res)
### BUGGY CODE ###

N, W = map(int, input().split())
p = []
for it in range(N):
    p.append(list(map(int,input().split())))
    
dp = [[0 for i in range(W+1)] for j in range(N+1)]
i = 0
for w, v in p:
    i += 1
    for w_limit in range(1, W+1):
        if w_limit < w:
            dp[i][w_limit]=dp[i-1][w_limit]
            continue
        if (dp[i-1][w_limit-w] + v) > dp[i-1][w_limit]:
            dp[i][w_limit] = dp[i-1][w_limit-w] + v
        else:
            dp[i][w_limit]=dp[i-1][w_limit]
print(max(max(dp)))

### FIXED CODE ###

N, W = map(int, input().split())
p = []
for it in range(N):
    p.append(list(map(int,input().split())))
    
dp = [[0 for i in range(W+1)] for j in range(N+1)]
i = 0
for w, v in p:
    i += 1
    for w_limit in range(1, W+1):
        if w_limit < w:
            dp[i][w_limit]=dp[i-1][w_limit]
            continue
        if (dp[i-1][w_limit-w] + v) > dp[i-1][w_limit]:
            dp[i][w_limit] = dp[i-1][w_limit-w] + v
        else:
            dp[i][w_limit]=dp[i-1][w_limit]
print(max(max(dp)))
### BUGGY CODE ###

N = int(input())

li = [int(s) for s in input().split()]

import functools
import operator

result = functools.reduce(operator.mul, li)

if result > 10**18:
    print(-1)
else:
    print(result)

### FIXED CODE ###

import sys

N = int(input())

Line = [int(s) for s in input().split()]
Line.sort()

ans = 1

for i in Line:
    ans = ans*i
    if ans > 10**18:
        print("-1")
        exit()
    elif ans == 0:
        print("0")
        exit()

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

n,k=map(int,input().split())
s=list(input())
import sys
input=sys.stdin.readline
s.reverse()
if k>=n:
    print(min(s)*n)
else:
    for i in range(min(k,5000)):
        t=list(reversed(s))
        u=t+s
        uu=u[:n]
        for j in range(1,n+1):
            x=u[j:j+n]
            if uu>x:
                uu=x
        s=uu
    print("".join(s))


### FIXED CODE ###

n,k=map(int,input().split())
s=list(input())
l=0
c=0
for i in range(n):
    if s[i]==min(s):
        c+=1
        l=max(l,c)
    else:
        c=0
import sys
input=sys.stdin.readline
s.reverse()
if (2**(k-1))*l>n:
    print(min(s)*n)
else:
    for i in range(min(k,13)):
        t=list(reversed(s))
        u=t+s
        uu=u[:n]
        for j in range(1,n+1):
            x=u[j:j+n]
            if uu>x:
                uu=x
        s=uu
    print("".join(s))
### BUGGY CODE ###

n = int(input())
ans = 0
ls = []
for _ in range(n):
    s = input()
    ls2 = []
    for i in range(10):
        ls2.append(s[i])
    ls3 = ''.join(sorted(ls2))
    for j in ls:
        if j == ls3:
            ans +=1
    ls.append(ls3)
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
ls = {}
for _ in range(n):
    s = ''.join(sorted(input()))
    if s in ls:
        ans += ls[s]
        ls[s] += 1
    else:
        ls[s] = 1
print(ans)
### BUGGY CODE ###

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

bc = []
for _ in range(m):
    b, c = map(int, input().split())
    bc += [c]*b

a.sort()
bc.sort(reverse=True)

for i in range(min(len(bc), n)):
    if a[i] < bc[i]:
        a[i] = bc[i]
    else: break

print(sum(a))


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [tuple(map(int, input().split())) for _ in range(m)]
bc.sort(reverse=True, key=lambda x: x[1])

bcs = []
for b, c in bc:
    if len(bcs) > n: break
    bcs.extend([c]*b)

a.extend(bcs)
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

class UnionFind:
    MAX_N = 0
    PAR  = [] 
    RANK = []

    def __init__(self,n):
        self.MAX_N = n
        self.PAR = [ i for i in range(n)]
        self.RANK= [ 0 ] * n

    def find(self,x):
        if self.PAR[x] == x:
            return x
        else:
            self.PAR[x] = self.find(self.PAR[x])
            return self.PAR[x] 

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.RANK[x] < self.RANK[y]:
            self.PAR[x] = y
        else:
            self.PAR[y] = x
            if self.RANK[x] == self.RANK[y]:
                self.RANK[x] += 1

    def same(self,x,y):
        return self.find(x) == self.find(y)

N,K,L = map(int,input().split())
path = UnionFind(N+1)
for _ in range(K):
    p,q = map(int,input().split())
    path.union(p,q)
rail = UnionFind(N+1)
for _ in range(L):
    p,q = map(int,input().split())
    rail.union(p,q)

Data = {}
for i in range(1,N+1):
    p = path.find(i)
    r = rail.find(i)
    k = str(p)+"-"+str(r)
    if k in Data.keys():
        Data[k] += 1
    else:
        Data[k] = 1

for i in range(1,N+1):
    p = path.find(i)
    r = rail.find(i)
    k = str(p)+"-"+str(r)
    print( Data[k], end= ' ')


### FIXED CODE ###

class UnionFind:
    MAX_N = 0
    PAR  = [] 
    RANK = []

    def __init__(self,n):
        self.MAX_N = n
        self.PAR = [ i for i in range(n)]
        self.RANK= [ 0 ] * n

    def find(self,x):
        if self.PAR[x] == x:
            return x
        else:
            self.PAR[x] = self.find(self.PAR[x])
            return self.PAR[x] 

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.RANK[x] < self.RANK[y]:
            self.PAR[x] = y
        else:
            self.PAR[y] = x
            if self.RANK[x] == self.RANK[y]:
                self.RANK[x] += 1

    def same(self,x,y):
        return self.find(x) == self.find(y)

N,K,L = map(int,input().split())
path = UnionFind(N+1)
for _ in range(K):
    p,q = map(int,input().split())
    path.union(p,q)
rail = UnionFind(N+1)
for _ in range(L):
    p,q = map(int,input().split())
    rail.union(p,q)

Data = {}
for i in range(1,N+1):
    p = path.find(i)
    r = rail.find(i)
    k = str(p)+"-"+str(r)
    if k in Data.keys():
        Data[k] += 1
    else:
        Data[k] = 1

for i in range(1,N+1):
    p = path.find(i)
    r = rail.find(i)
    k = str(p)+"-"+str(r)
    print( Data[k], end= ' ')
### BUGGY CODE ###

n,k=map(int,input().split())
A=list(map(int,input().split()))
cc=1
for j in range(k):
  cc*=A[j]

for i in range(k,n):
  pp=A[i]*cc//A[i-k]
  if pp>cc:print('Yes')
  else:print('No')
  
  cc=pp

### FIXED CODE ###

from collections import deque

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


for i in range(k,n):
  if A[i]>A[i-k]:print('Yes')
  else:print('No')
### BUGGY CODE ###

n=int(input())
a=[]
ans=1e12
l=int(n**0.5)+2
for i in range(1,l):
  if i in a:
    continue
  elif n%i==0:
    a.append(i)
    a.append(n//i)
    ans=min(ans,(i+n//i-2))
print(ans) 

### FIXED CODE ###

n=int(input())
a=[]
ans=1e12
l=int(n**0.5)+2
for i in range(1,l):
  if n%i==0 and i not in a:
    a.append(i)
    a.append(n//i)
    ans=min(ans,(i+n//i-2))
print(ans)
### BUGGY CODE ###

x = int(input())
h = x

for i in range(2,10**5):
    if x%i == 0:
        h = i
        break


for i in range(1, 10**9):
    a = i
    b = h-i
    if a**5-b**5 == x:
        print(a, b)
        exit(0)
    b = i-h
    if a**5-b**5 == x:
        print(a, b)
        exit(0)

### FIXED CODE ###

x = int(input())

for a in range(-118, 120):
    for b in range(-119, 119):
        if a**5-b**5 == x:
            print(a, b)
            exit()
### BUGGY CODE ###

import sys

stdin = sys.stdin

read_int = lambda : list(map(int,stdin.readline().split()))

N,M = read_int()
price_howmany = {}
price_list = []

for _ in range(N):
    tmp = read_int()
    if tmp[0] not in price_list:
        price_list.append(tmp[0])
    if tmp[0] in price_howmany:
        price_howmany[tmp[0]] += tmp[1]
    else:
        price_howmany[tmp[0]] = tmp[1]
price_list.sort()

def solve():
    price = 0
    global M
    for low_price in price_list:
        many = min(M,price_howmany.pop(low_price))
        price += many * low_price
        M -= many
        if M == 0: break
    print(price)

if __name__ == "__main__":
    solve()

### FIXED CODE ###

# from collections import defaultdict
# N,M = list(map(int,input().split()))
# price_howmany = defaultdict(int)
import sys

stdin = sys.stdin

read_int = lambda : list(map(int,stdin.readline().split()))

N,M = read_int()
price_howmany = {}
# price_list = []

price_set = set()
for _ in range(N):
    tmp = read_int()
    # if tmp[0] not in price_set:
        # price_list.append(tmp[0])
    price_set.add(tmp[0])
    if tmp[0] in price_howmany:
        price_howmany[tmp[0]] += tmp[1]
    else:
        price_howmany[tmp[0]] = tmp[1]
# price_list.sort(reverse=True)
price_list = sorted(list(price_set))

# price_howmany = dict(price_howmany)

def solve():
    price = 0
    global M
    # while M > 0:
        # low_price = min(price_howmany.keys())
        # low_price = price_list.pop()
        # many = min(M,price_howmany.pop(low_price))
        # price += many * low_price
        # M -= many
    for low_price in price_list:
        many = min(M,price_howmany.pop(low_price))
        price += many * low_price
        M -= many
        if M == 0: break
    print(price)

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

K,S = map(int,input().split())
x,y,z = 0,0,0
n = 0

for i in range(K+1):
    x = i
    if x == S:
        n += 1
        break
    for j in range(K+1):
        y = j
        if x+y == S:
            n += 1
            break
        for k in range(K+1):
            z = k
            if x+y+z == S:
                n += 1

print(n)


### FIXED CODE ###

K,S = map(int,input().split())
x,y,z = 0,0,0
n = 0

for i in range(K+1):
    x = i
    for j in range(K+1):
        y = j
        z = S-(x+y)
        if 0 <= z <=K:
            n += 1

print(n)
### BUGGY CODE ###

N = int(input())
S = str(input())


#S_R = []
#S_G = []
#S_B = []
R = 0
G = 0
B = 0

for i in range(N):
    s = S[i]
    if (s == 'R'):
        #_R.append(i)
        R +=1
    if (s == 'G'):
        #S_G.append(i)
        G +=1
    if (s == 'B'):
        #S_B.append(i)
        B +=1

count = R * G * B

#count = len(S_R) * len(S_G) * len(S_B)
#rgb = {'R', 'G', 'B'}


#for i in range(N):
    #for j in range(i):
        #x = S[j::i]
        #for a, b, c in zip(x, x[1:], x[2:]):
            #if({a,b,c} == rgb):
                #count -=1

for i in range(N):
    for j in range(N):
        if(i + j*2 >= N):
            continue
        if((S[i] != S[i + j]) & (S[i + j] != S[i + 2 * j]) & (S[i + 2 * j] != S[i])):
            count -= 1




print(count)

### FIXED CODE ###

n = int(input())
s = input()
 
r, b, g = 0, 0, 0
for i in range(n):
    if s[i] == 'R':
        r += 1
    if s[i] == 'G':
        g += 1
    if s[i] == 'B':
        b += 1
ans = r * g * b
 
for i in range(n):
    for j in range(1, n // 2 + 1):
        if i + 2 * j >= n:
            break
        if s[i] != s[i+j] and s[i] != s[i+2*j] and s[i+j] != s[i+2*j]:
            ans -= 1
 
print(ans)
### BUGGY CODE ###

n=int(input())

for k in range(1,n+1):

    ans=0
    for x in range(1,51):
        if k-x**2<=0:
            break
        for y in range(1,51):
            if k-x**2- y**2<=0:
                break

            for z in range(1,51):
                
                if x**2 + y**2 + z**2 +x*y + y*z + z*x ==k:
                    ans+=1
    print(ans)


### FIXED CODE ###

n=int(input())

ans=[0]*(n+1)

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            f= x**2 + y**2 + z**2 + x*y + y*z + z*x
            if f<=n:
                ans[f]+=1

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