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

from math import factorial

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

#答え用の関数
ans = 0
#Σ(k 1~n) nCk = 2^n
ans += (2**n)%(10**9+7)
nCa = (factorial(n)//(factorial(a)*factorial(n-a)))%(10**9+7)
nCb = (factorial(n)//(factorial(b)*factorial(n-b)))%(10**9+7)
ans -= (nCa+nCb+1)
ans = ans%(10**9+7)
print(ans)

### FIXED CODE ###

n,a,b = map(int,input().split())
m = 10**9+7

def nCr(n_, r_, m_):
  c = min(r_ , n_ - r_)
  bunshi = 1
  bunbo = 1
  for i in range(1,c+1):
    bunshi = bunshi * (n_+1-i) % m_
    bunbo = bunbo * i % m_
  return bunshi * pow(bunbo, m_-2, m_) % m_


ans = pow(2,n,m)-1
ans -= nCr(n,a,m)
ans %= m
ans -= nCr(n,b,m)
ans %= m
print(ans)
### BUGGY CODE ###

from collections import deque
q = deque([])

def get_root(i):
    while True:
        if parent[i] == -1:
            return i
        i = parent[i]

def bfs(i):
    global l
    c = 0
    q.append(i)
    while True:
        if len(q) == 0:
            break
        p = q.popleft()
        l.append(p)
        c += 1
        if not children[p] == -1:
            for j in children[p]:
                q.append(j)
    return c

n, m = map(int, input().split())
p = list(map(int, input().split()))
parent = [-1] * n
children = [-1] * n
d = [0] * n
root = []
rank = []
num = ["a"] * n
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    if num[x] == "a":
        num[x] = [y]
    else:
        num[x].append(y)
    if num[y] == "a":
        num[y] = [x]
    else:
        num[y].append(x)
    if d[x] == d[y] == 0:
        root.append(x)
        rank.append(1)
        children[x] = [y]
        parent[y] = x
        d[x] = 1
        d[y] = 1
    elif d[x] == 1 and d[y] == 0:
        r = get_root(x)
        children[r].append(y)
        parent[y] = r
        d[y] = 1
    elif d[x] == 0 and d[y] == 1:
        r = get_root(y)
        children[r].append(x)
        parent[x] = r
        d[x] = 1
    else:
        s = get_root(x)
        t = get_root(y)
        if not s == t:
            i = rank[root.index(s)]
            j = rank[root.index(t)]
            if i >= j:
                parent[t] = s
                children[s].append(t)
                if i == j:
                    rank[root.index(s)] += 1
            else:
                parent[s] = t
                children[t].append(s)

ans = 0
for i in range(n):
    if parent[i] == -1 and children[i] != -1:
        l, p0 = [], []
        bfs(i)
        for j in l:
            pp = p[j] - 1
            p0.append(pp)
        l = l + p0
        k = len(l)
        ans += k - len(set(l))
    elif parent[i] == -1:
        if p[i] - 1 == i:
            ans += 1
print(ans)

### FIXED CODE ###

def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
        elif rank[s] > rank[t]:
            root[root_t] = root_s
        else:
            root[root_s] = root_t

def same(s, t):
    if get_root(s) == get_root(t):
        return True
    else:
        return False

n, m = map(int, input().split())
p = list(map(int, input().split()))
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().split())
    unite(x - 1, y - 1)
ans = 0
for i in range(n):
    if get_root(i) == get_root(p[i] - 1):
        ans += 1
print(ans)
### BUGGY CODE ###

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

mod = 10**9+7

all_num = k**n
ans = 0

dp = [0]*(k+1)

for i in range(k):
    tmp = k-i
    #print(tmp)
    #print(tmp,tmp,tmp)
    kazu = 1
    kakeru = 2
    heru = 0
    #print(tmp,k)
    for i in range(k//tmp-1):
        #print(i)
        heru += dp[tmp*kakeru]
        kazu += 1
        kakeru += 1
    """
    while tmp * kakeru <= k:
        heru += dp[tmp*kakeru]
        kazu += 1
        kakeru += 1
        #print(tmp*kakeru,k)
    """ 
    
    if tmp == 1:
        ans += all_num
        ans %= mod
        break
    kazu = pow(kazu,n,mod)-heru
    #kazu = kazu**n-heru
    ans += tmp*(kazu)
    all_num -= (kazu)
    #print(tmp,kazu,n,heru)
    dp[tmp] = kazu
    ans %= mod
    #print(ans,tmp,kazu)
    
print(ans)

### FIXED CODE ###

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

mod = 10**9+7

all_num = pow(k,n,mod)
#all_num = k**n


ans = 0

dp = [0]*(k+1)

for i in range(k):
    tmp = k-i
    #print(tmp)
    #print(tmp,tmp,tmp)
    kazu = 1
    kakeru = 2
    heru = 0
    
    if tmp == 1:
        ans += all_num
        ans %= mod
        break
    
    #print(tmp,k)
    for i in range(k//tmp-1):
        #print(i)
        heru += dp[tmp*kakeru]
        kazu += 1
        kakeru += 1
    """
    while tmp * kakeru <= k:
        heru += dp[tmp*kakeru]
        kazu += 1
        kakeru += 1
        #print(tmp*kakeru,k)
    """ 
    
    kazu = pow(kazu,n,mod)-heru
    #kazu = kazu**n-heru
    ans += tmp*(kazu)
    all_num -= (kazu)
    #print(tmp,kazu,n,heru)
    dp[tmp] = kazu
    ans %= mod
    #print(ans,tmp,kazu)
    
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
num = 1
for i in range(0,N):
    if A[i]==0:
      	num=0
      	break
    else:
      num *=A[i]

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

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
num = 1
for i in range(0,N):
    if A[i]==0:
      	num=0
      	break
for i in range(0,N):
    if num>10**18:
        break
    else:
        num *=A[i]
if num>10**18:
    print(-1)
else:
    print(num)
### BUGGY CODE ###

N,Q = map(int, input().split())
import copy
import sys

sys.setrecursionlimit(10**6)
es = {}
for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    if a in es:
        es[a].append(b)
    else:
        es[a] = [b]


point_root = [0] * N
query = [None]
for i in range(Q):
    p,x = map(int, input().split())
    point_root[p-1] += x 

ans = [0] * N
visited = [False] * N
ans[0] = point_root[0]
visited[0] = True
def solve(node, point):
    ans[node] = point
    visited[node] = True
    if all(visited) == True:
        print(*ans)
        exit()

    if es.get(node, None) != None:
        next_nodes = copy.deepcopy(es[node]) # これからポイントを足し行くやつら

        for i in next_nodes:
            solve(i, point+point_root[i])
solve(0, point_root[0])

### FIXED CODE ###

N,Q = map(int, input().split())
import copy
import sys

sys.setrecursionlimit(10**6)
es = [[] for i in range(N)]

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


point = [0] * N

for i in range(Q):
    p,x = map(int, input().split())
    point[p-1] += x 

ans = [0] * N
ans[0] = point[0] # 一番上の根なのでこれだけ
visited = [False] * N
visit_cnt = 1
from collections import deque
nexts = deque([0])
while len(nexts) >= 1:
    now = nexts.popleft()
    visited[now] = True

    for next in es[now]:
        if visited[next] == True:
            continue
        nexts.append(next)
        ans[next] = ans[now] + point[next]


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

n = int(input())
l = []
r = [0]*10**5
res = 0

num = 0

for i in range(n):
    an = list(input())
    an.sort()
    an = "".join(map(str, an))
    #print(an)
    if an not in l:
        l.append(an)
        num += 1
    r[l.index(an)] += 1

z = 0
for i in range(1,max(r)+1):
    #print(j)
    z += i-1
    if i in r:
        res += z*r.count(i)
else:
    print(res)


### FIXED CODE ###

# original_author prd_xxx
from collections import Counter

N = int(input())
S = [input() for i in range(N)]

# collections.Counter()を使うと0回目の時にバグらないので23行目elseを省略可能
ctr = Counter()
ctr = {}
ans = 0

for s in S:
    # 文字列を昇順に並べ替え
    # 文字列をリスト化し、sortしたものを文字列化
    a = ''.join(sorted(list(s)))

    # ソート済み文字列が以前に存在していたら、答えに前回の合計値を加算する
    # 1..0 2..1 3..3 4..6 5..10 ... 組み合わせの数n(n-1)/2があり、
    # 最後にO(n)で計算も可能だが、冗長。
    # 一個ずつ処理していくと、
    # 1..0 2..+1(1) 3..+2(3) 4..+3(6) 5..+4(10)の増加になる
    if a in ctr:
        ans += ctr[a]
    else:
        ctr[a] = 0

    ctr[a] += 1

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

import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
Q = int(input())
qs = list(map(int, input().split()))
cs = [0] * (N + 1)
c = []
d = []
for i in range(N):
  cs[i + 1] = cs[i] + (S[i] == "M")
  if S[i] == "C": c.append(i)
  if S[i] == "D": d.append(i)
ccs = [0] * (len(c) + 1)
for i in range(len(c)):
  ccs[i + 1] = ccs[i] + cs[c[i]]
#print(c, ccs)
for k in qs:
  res = 0
  for i in d:
    if S[i] != "D": continue
    l = bl(c, i)
    r = bl(c, i + k)
    res += max(0, ccs[r] - ccs[l] - cs[i] * (r - l))
  print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
Q = int(input())
qs = list(map(int, input().split()))
cs = [0] * (N + 1)
c = []
d = []
for i in range(N):
  cs[i + 1] = cs[i] + (S[i] == "M")
  if S[i] == "C": c.append(i)
  if S[i] == "D": d.append(i)
ccs = [0] * (N + 1)
ccounts = [0] * (N + 1)
for i in range(N):
  ccs[i + 1] = ccs[i] + cs[i] * (S[i] == "C")
  ccounts[i + 1] = ccounts[i] + (S[i] == "C")

#print(cs, c)
#print(ccs)
for k in qs:
  res = 0
  for i in d:
    l = i
    r = min(N, i + k)
    res += max(0, ccs[r] - ccs[l] - cs[i] * (ccounts[r] - ccounts[l]))
  print(res)
### BUGGY CODE ###

N=int(input())
xy=[tuple(map(int,input().split())) for _ in range(N)]
ans=0
for i in range(N):
    for j in range(i+1,N):
        ans=max(ans,abs(xy[i][0]-xy[j][0])+abs(xy[i][1]-xy[j][1]))
print(ans)

### FIXED CODE ###

N=int(input())
xy=[tuple(map(int,input().split())) for _ in range(N)]
ans=0
zmi=10**10
zma=-10**10
wmi=10**10
wma=-10**10
for x,y in xy:
    zmi=min(zmi,x+y)
    zma=max(zma,x+y)
    wmi=min(wmi,x-y)
    wma=max(wma,x-y)
print(max(zma-zmi,wma-wmi))
### BUGGY CODE ###

from itertools import product
D, G = map(int, input().split())
pc = [tuple(map(int, input().split())) for _ in range(D)]
p = [x[0] for x in pc]
c = [x[1] for x in pc]
result = sum(p)
for nums in product(*map(range, [pp + 1 for pp in p])):
    n = sum(nums)
    if n >= result:
        continue
    point = 0
    for i, num in enumerate(nums):
        point += (i + 1) * 100 * num
        if num == p[i]:
            point += c[i]
    if point >= G:
        result = n
print(result)

### FIXED CODE ###

import functools
D, G = map(int, input().split())
G = G // 100
sumn = 0
ns = [0] * (D + 1)
cs = [0] * (D + 1)
for i in range(1, D + 1):
    n, c = map(int, input().split())
    ns[i] = n
    cs[i] = c // 100
    sumn += n

minn = [0] * (D + 1)
for i in range(1, D + 1):
    minn[i] = min(ns[1:i+1])

@functools.lru_cache(maxsize=None)
def f(i, rn):
    if i == 1:
        if ns[1] < rn:
            return -1
        p = rn
        if ns[1] == rn:
            p += cs[1]
        return p
    if rn < minn[i]:
        p = 0
        for j in range(i, 0, -1):
            n = min((ns[j], rn))
            p += j * n
            if n == rn:
                break
            rn -= n
        return p
    maxp = 0
    for n in range(min((ns[i], rn)) + 1):
        p = i * n
        if n == ns[i]:
            p += cs[i]
        np = f(i - 1, rn - n)
        if np >= 0:
            p += np
            if maxp < p:
                maxp = p
    return maxp

mn = 1
mx = sumn
while mn < mx:
    x = mn + ((mx - mn) // 2)
    if G <= f(D, x):
        mx = x
    else:
        mn = x + 1
print(mn)
### BUGGY CODE ###

from collections import Counter

def solve():
    MOD = 10**9 + 7
    maxA = 10**6

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

    isPrimes = [False]*2 + [True]*(maxA-1)
    minFs = [1] * (maxA+1)
    for i in range(2, int(maxA**0.5) + 1):
        if isPrimes[i]:
            for x in range(i*i, maxA+1, i):
                isPrimes[x] = False
                minFs[x] = i

    def getPrimeFactors(x):
        anss = []
        while minFs[x] > 1:
            anss.append(minFs[x])
            x //= minFs[x]
        if x != 1:
            anss.append(x)
        return anss

    PFss = []
    Primes = set()
    for A in As:
        PFs = getPrimeFactors(A)
        cnt = Counter(PFs)
        PFss.append(cnt)
        Primes |= cnt.keys()

    cntP = Counter()
    for PFs in PFss:
        for key, num in PFs.items():
            cntP[key] = max(cntP[key], num)

    lcmA = 1
    for key, num in cntP.items():
        lcmA *= pow(key, num, MOD)
        lcmA %= MOD

    def getInvs(n, MOD):
        invs = [1] * (n+1)
        for x in range(2, n+1):
            invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
        return invs

    invs = getInvs(10**6, MOD)

    ans = 0
    for A in As:
        ans += lcmA * invs[A]
        ans %= MOD

    print(ans)

solve()


### FIXED CODE ###

from collections import Counter

def solve():
    MOD = 10**9 + 7
    maxA = 10**6

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

    isPrimes = [False]*2 + [True]*(maxA-1)
    minFs = [1] * (maxA+1)
    for i in range(2, int(maxA**0.5) + 1):
        if isPrimes[i]:
            for x in range(i*i, maxA+1, i):
                isPrimes[x] = False
                minFs[x] = i

    def getPrimeFactors(x):
        anss = []
        while minFs[x] > 1:
            anss.append(minFs[x])
            x //= minFs[x]
        if x != 1:
            anss.append(x)
        return anss

    PFss = []
    Primes = set()
    for A in As:
        PFs = getPrimeFactors(A)
        cnt = Counter(PFs)
        PFss.append(cnt)
        Primes |= cnt.keys()

    cntP = Counter()
    for PFs in PFss:
        for key, num in PFs.items():
            cntP[key] = max(cntP[key], num)

    lcmA = 1
    for key, num in cntP.items():
        lcmA *= pow(key, num, MOD)
        lcmA %= MOD

    def getInvs(n, MOD):
        invs = [1] * (n+1)
        for x in range(2, n+1):
            invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
        return invs

    invs = getInvs(10**6, MOD)

    ans = 0
    for A in As:
        ans += lcmA * invs[A]
        ans %= MOD

    print(ans)

solve()
### BUGGY CODE ###

n = int(input())
x = input()

sdict = dict()
def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")

x_i = int(x, 2)
solve = 0
for i in range(n):
    if x[i] == "0":
        solve = x_i+2**(n-i-1)
    else:
        solve = x_i-2**(n-i-1)
    count = 0
    solved = []
    while solve > 0:
        if solve in sdict:
            count += sdict[solve]
            break
        else:
            solved.append(solve)
            solve = solve % popcount(solve)
            count+=1

    c = count
    for i in solved:
        sdict[i] = c
        c-=1

    print(count)

### FIXED CODE ###


n = int(input())
x = input()

def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")

def ans(n,x):
    x_i = int(x, 2)
    x_orig = popcount(x_i)
    x_i_t = x_i % (x_orig+1)
    if x_orig != 1:
        x_i_b = x_i % (x_orig-1)
    else:
        x_i_b = x_i
    solve = 0
    for i in range(n):
        x_count = x_orig
        if x[i] == "0":
            x_count += 1
            solve = x_i_t + pow(2,n-1-i,x_count)
        else:
            x_count -= 1
            if x_count != 0:
                solve = x_i_b - pow(2,n-1-i,x_count)
            else:
                print(0)
                continue
        count = 0

        if x_count != 0 :
            solve = solve % x_count
            count+=1

        while solve > 0:
            solve = solve % popcount(solve)
            count+=1

        print(count)

    
ans(n,x)
### BUGGY CODE ###

n,p= map(int,input().split())
for i in range(round(p**(1/n))+1,0,-1):
    if p%(i**n)==0:
        print(i)
        exit()

### FIXED CODE ###

n,p= map(int,input().split())
for i in range(round(p**(1/n)),0,-1):
    if p%(i**n)==0:
        print(i)
        exit()
### BUGGY CODE ###

n,w = map(int,input().split())
weight = []
value = []
for i in range(n):
  a,b= map(int,input().split())
  weight.append(a)
  value.append(b)

dp = [[0]*(w+1) for i in range(n+1)]
for i in range(n):
  for j in range(w+1):
    if j - weight[i] >= 0:
      dp[i+1][j] = max(dp[i][j],dp[i][j-weight[i]] + value[i])
    else:
      dp[i+1][j] = dp[i][j]

print(dp[n][w])


### FIXED CODE ###

n,w = map(int,input().split())
weight = []
value = []
for i in range(n):
  a,b= map(int,input().split())
  weight.append(a)
  value.append(b)

dp = [[0]*(w+1) for i in range(n+1)]
for i in range(n):
  for j in range(w+1):
    if j - weight[i] >= 0:
      dp[i+1][j] = max(dp[i][j],dp[i][j-weight[i]] + value[i])
    else:
      dp[i+1][j] = dp[i][j]

print(dp[n][w])
### BUGGY CODE ###

N = int(input())
S =list(map(int,input()))

ans = [[[0 for _ in range(10)] for _ in range(10)]for _ in range(10)]
ans_total = 0

for i,s in enumerate(S):
  Xoo = list(set(S[:i]))
  ooX = list(set(S[i+1:]))
  #print(s,Xoo,ooX)
  for r in Xoo:
    for t in ooX:
      #print(r,s,t)
      if ans[r][s][t] == 0:
        ans_total += 1
      ans[r][s][t] = 1
  if ans_total == 999:
    break
print(ans_total)

### FIXED CODE ###

N = int(input())
S =list(map(int,input()))

ans = 0

for x in [0,1,2,3,4,5,6,7,8,9]:
  if x in S:
    x_index = S.index(x)
    for y in [0,1,2,3,4,5,6,7,8,9]:
      if y in S[x_index+1:]:
        y_index = S[x_index+1:].index(y)
        for z in [0,1,2,3,4,5,6,7,8,9]:
          if z in S[x_index + 1 + y_index+1:]:
            ans += 1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

def main():
    n = int(input())
    h = np.array(input().split(), dtype='int')

    ans = 0

    for i in range(n - 1):
        times_move = 0
        for j in range(n - i - 1):
            if h[i + j] >= h[i + j + 1]:
                times_move += 1
            else:
                break
        if times_move > ans:
            ans = times_move

    print(ans)


main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

def main():
    n = int(input())
    h = np.array(input().split(), dtype='int')

    ans = 0
    i = 0

    while i < n:
        times_move = 0
        for j in range(n - i - 1):
            if h[i + j] < h[i + j + 1]:
                break
            else:
                times_move += 1
        if times_move > ans:
            ans = times_move
        if n - i - 1 <= ans:
            break
        i += times_move + 1

    print(ans)


main()
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque

INF = 1 << 50


def run():
    N, K = map(int, sysread().split())
    A = list(map(int, sysread().split()))

    l = 0
    r = 10**9
    while int(l) != int(r):
        test = (l + r) / 2
        sum = 0
        for a in A:
            sum += math.ceil(a / test) - 1

        if sum > K:
            l = test
        elif a < K:
            r = test
        else:# sum == K
            r = test
    if int(l) == 0:
        print(1)
        return
    if int(l) == l:
        sum = 0
        for a in A:
            sum += math.ceil(a / int(l)) - 1
        if sum == K:
            print(int(l))
            return

    print(int(l)+1)

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque

INF = 1 << 50


def run():
    N, K = map(int, sysread().split())
    A = list(map(int, sysread().split()))

    l = 0
    r = 10**9
    while int(l) != int(r):
        #print(l, r)
        test = (l + r) / 2
        sum = 0
        for a in A:
            sum += math.ceil(a / test) - 1

        if sum > K:
            l = test
        elif sum < K:
            r = test
        else:# sum == K
            r = test
        if int(r) == r and r-l < 1:
            print(int(r))
            return

    if int(l) == 0:
        print(1)
        return
    if int(l) == l:
        sum = 0
        for a in A:
            sum += math.ceil(a / int(l)) - 1
        if sum == K:
            print(int(l))
            return

    print(int(l)+1)

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

N = int(input())

lis = []

for n in range(N):
  s = input()
  if not s in lis:
    lis.append(s)

print(len(lis))

### FIXED CODE ###

N = int(input())

lis = []

for n in range(N):
  lis.append(input())

s = set(lis)
print(len(s))
### BUGGY CODE ###

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


for _ in range(m):
  a = A.pop() // 2
  A.insert(bisect.bisect_left(A,a),a)
print(sum(A))

### FIXED CODE ###

import bisect
import heapq
n,m = map(int,input().split())
A = list(map(int,input().split()))
A = list(map(lambda x: x*(-1), A))


heapq.heapify(A)


for _ in range(m):
  a = -heapq.heappop(A)//2
  heapq.heappush(A,-a)
print(-sum(A))
### BUGGY CODE ###

n = int(input())
for i in range(1, n + 1):
    count = 0
    num = int(n ** 0.5)
    for j in range(1, num + 1):
        for k in range(1, num + 1):
            for l in range(1, num + 1):
                if j ** 2 + k ** 2 + l ** 2 + j * k + k * l + l * j == i:
                    count += 1
    print(count)

### FIXED CODE ###

n = int(input())
num = [0] * 10001
for i in range(1, 142):
    for j in range(1, 142):
        for k in range(1, 142):
            temp = i + j + k
            if temp % 2 == 0:
                if i + j > k and j + k > i and k + i > j:
                    temp2 = (i ** 2 + j ** 2 + k ** 2) // 2
                    if 0 <= temp2 <= 10000:
                        num[temp2] += 1
for i in range(1, n + 1):
    print(num[i])
### BUGGY CODE ###

from functools import lru_cache
N,W=map(int,input().split())
weights0,profits0 = [0]*N, [0]*N
for i in range(N):
    weights0[i],profits0[i] = map(int,input().split())
weights0 = tuple(weights0)
profits0 = tuple(profits0)

@lru_cache(maxsize=1024)
def knapsack_recursive(weights, profits, capacity, currentIndex):
    if capacity <= 0 or currentIndex >= len(profits): return 0
    profit = 0
    if weights[currentIndex] <= capacity:
        profit = profits[currentIndex] + knapsack_recursive(weights, profits, capacity - weights[currentIndex], currentIndex + 1)
    tmp = knapsack_recursive(weights, profits, capacity, currentIndex + 1)
    if tmp > profit:
        profit = tmp  
    return profit
  
def main():
    res = knapsack_recursive(weights0, profits0, W, 0)
    print(res)
if __name__ == "__main__":
	main()

### FIXED CODE ###

def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()
### BUGGY CODE ###

init = input().split(' ')
init = [int(i) for i in init]
n,m= init[0],init[1]

ab = []

try:
	while True:
		inp1 = input().split(' ')
		inp1 = [int(i) for i in inp1]
		ab.append([inp1[0],inp1[1]])
except:
	pass

ab.sort()
total = sum([ab[j][0]*ab[j][1] for j in range(n)])
deltarget = sum([ab[j][1] for j in range(n)]) - m

while deltarget > 0:
	if ab[len(ab)-1][1]>0:
		total -= ab[len(ab)-1][0]
		ab[len(ab)-1][1] -= 1
		deltarget -= 1
		
	else:
		ab.pop(len(ab)-1)

print(total)

### FIXED CODE ###

init = input().split(' ')
init = [int(i) for i in init]
n,m= init[0],init[1]

ab = []

try:
	while True:
		inp1 = input().split(' ')
		inp1 = [int(i) for i in inp1]
		ab.append([inp1[0],inp1[1]])
except:
	pass

ab.sort()
total = sum([ab[j][0]*ab[j][1] for j in range(n)])
deltarget = sum([ab[j][1] for j in range(n)]) - m

while deltarget > 0:
	if deltarget - ab[len(ab)-1][1] > 0:
		total -= ab[len(ab)-1][0]*ab[len(ab)-1][1]
		deltarget -= ab[len(ab)-1][1]
		ab.pop(len(ab)-1)
	else:
		total -= ab[len(ab)-1][0]*deltarget
		break

print(total)