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

import sys
from collections import deque


def bfs(links, s, limit, bits):
    not_reachable = (1 << len(links)) - 1
    q = deque([(0, s, -1)])
    while q:
        cost, v, p = q.popleft()
        if cost > limit:
            break
        not_reachable ^= bits[v]
        cost += 1
        q.extend((cost, u, v) for u in links[v] if u != p)
    return not_reachable


def solve(n, k, ab):
    if k == 1:
        return n - 2

    links = [set() for _ in range(n)]
    for a, b in ab:
        a -= 1
        b -= 1
        links[a].add(b)
        links[b].add(a)

    limit = k // 2
    bits = [1 << i for i in range(n)]
    if k % 2 == 0:
        ans = min(bin(bfs(links, v, limit, bits)).count('1') for v in range(n))
    else:
        dists = [bfs(links, v, limit, bits) for v in range(n)]
        ans = min(bin(dists[a - 1] & dists[b - 1]).count('1') for a, b in ab)
    return ans


n, k = map(int, sys.stdin.buffer.readline().split())
ab = map(int, sys.stdin.buffer.read().split())
ab = list(zip(ab, ab))
print(solve(n, k, ab))


### FIXED CODE ###

import sys
from collections import deque


def bfs(links, s, limit):
    not_reachable = [True] * len(links)
    q = deque([(0, s, -1)])
    while q:
        cost, v, p = q.popleft()
        if cost > limit:
            break
        not_reachable[v] = False
        cost += 1
        q.extend((cost, u, v) for u in links[v] if u != p)
    return not_reachable


def solve(n, k, ab):
    if k == 1:
        return n - 2

    links = [set() for _ in range(n)]
    for a, b in zip(ab[0::2], ab[1::2]):
        a -= 1
        b -= 1
        links[a].add(b)
        links[b].add(a)

    ans = n
    thr = k // 2
    if k % 2 == 0:
        ans = min(sum(bfs(links, v, thr)) for v in range(n))
    else:
        dists = [bfs(links, v, thr) for v in range(n)]
        for a, b in zip(ab[0::2], ab[1::2]):
            a -= 1
            b -= 1
            ans = min(ans, sum(d1 and d2 for d1, d2 in zip(dists[a], dists[b])))
    return ans


n, k, *ab = map(int, sys.stdin.buffer.read().split())
print(solve(n, k, ab))
### BUGGY CODE ###

def main():
    import sys
    import time
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N = int(input())
    P = [int(a) for a in input().strip().split()]
    G = [[min(n, N-n-1,i, N-i-1) for i in range(N)] for n in range(N)]
    Gflag = [[1] * N for _ in range(N)]
    ans = 0

    vecs = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    def prg():
        for n in range(N):
            print(G[n], Gflag[n])

    def update(row, col, cost):
        G[row][col] = cost
        for vr, vc in vecs:
            nrow, ncol = row + vr, col + vc
            if nrow < 0 or nrow >= N or ncol < 0 or ncol >= N:
                continue
            if G[nrow][ncol] > cost + Gflag[row][col]:
                update(nrow, ncol, cost + Gflag[row][col])

        return None        

    # prg()
    for p in P:
        # print('p = {}'.format(p))
        row, col = (p-1) // N, (p-1) % N
        ans += G[row][col]
        Gflag[row][col] = 0
        update(row, col, G[row][col])
        # prg()
        # print('ans = {}'.format(ans))

    print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    import time
    from collections import deque
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N = int(input())
    P = [int(a) for a in input().strip().split()]
    G = [[min(n, N-n-1,i, N-i-1) for i in range(N)] for n in range(N)]
    Gflag = [[1] * N for _ in range(N)]
    ans = 0

    vecs = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    for p in P:
        row, col = (p-1) // N, (p-1) % N
        ans += G[row][col]
        Gflag[row][col] = 0
        q = deque([(G[row][col], row, col)])
        while q:
            cost, row, col = q.popleft()
            if row > 0:
                if G[row-1][col] > cost + Gflag[row][col]:
                    G[row-1][col] = cost + Gflag[row][col]
                    q.append((cost+Gflag[row][col], row-1, col))
            if row < N-1:
                if G[row+1][col] > cost + Gflag[row][col]:
                    G[row+1][col] = cost + Gflag[row][col]
                    q.append((cost+Gflag[row][col], row+1, col))
            if col > 0:
                if G[row][col-1] > cost + Gflag[row][col]:
                    G[row][col-1] = cost + Gflag[row][col]
                    q.append((cost+Gflag[row][col], row, col-1))
            if col < N-1:
                if G[row][col+1] > cost + Gflag[row][col]:
                    G[row][col+1] = cost + Gflag[row][col]
                    q.append((cost+Gflag[row][col], row, col+1))

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

n, k = map(int, input().split())
p = list(map(int, input().split()))
l = []
m = []
s = []
j = 0
for i in range(1, 1001):
    j += i
    s.append(j)

for i in range(n-k+1):
    l.append(p[i:i+k])
    m.append(sum(p[i:i+k]))
Max_index = m.index(max(m))

ll = l[Max_index]
ans = 0
for i in ll:
    ans += s[i-1]/i 
print(ans) 

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
l = []
y = 0
for x in range(1, 1001):
    y += x
    l.append(y/x)
m = []
for i in p:
    m.append(l[i-1])
s = [0]
z = 0
for i in m:
    z += i
    s.append(z)
ans = 0
for i in range(n-k+1):
    ans = max(ans, s[i+k] - s[i])
print(ans)
### BUGGY CODE ###

N = int(input())
power=1

for i in range(1,N+1):
    power=power*i
print(power%(pow(10,9)+7))


### FIXED CODE ###

N = int(input())
x=1
for i in range(1,N+1):
    x=i*x%(pow(10,9)+7)
print(x)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = []
for i in range(m):
    b, c = map(int, input().split())
    bc += [c] * b
abc = a + bc
abc.sort(reverse=True)
print(sum(abc[:len(a)]))

### FIXED CODE ###

from collections import Counter

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

abc = Counter(a).most_common()
for i in range(m):
    b, c = map(int, input().split())
    abc.append((c, b))

abc.sort(reverse=True)

ans = 0
count = n
for c, b in abc:
    rep = min(count, b)
    ans += c * rep
    count -= rep
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))
    M = max(A)
    dig = len(bin(M)) - 2
    MOD = 10 ** 9 + 7
    ans = 0
    d = {i: 0 for i in range(dig)}
    for a in A:
        a = bin(a)[2:]
        for i in range(len(a)):
            if a[-(i+1)] == '1':
                d[i] += 1
    for i in range(dig):
        ans += d[i] * (n - d[i]) * pow(2, i, MOD)
        ans %= MOD
    print(ans)
main()


### FIXED CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))
    M = max(A)
    dig = len(bin(M)) - 2
    MOD = 10 ** 9 + 7
    ans = 0
    d = {i: [0, 0] for i in range(dig)}
    for a in A:
        a = bin(a)[2:].zfill(dig)
        for i in range(len(a)):
            if a[-(i+1)] == '0':
                d[i][0] += 1
            else:
                d[i][1] += 1
    for i in range(dig):
        ans += d[i][0] * d[i][1] * pow(2, i, MOD)
        ans %= MOD
    print(ans)
main()
### BUGGY CODE ###

H, W = map(int, input().split())
C = [input() for i in range(H)]

import sys
sys.setrecursionlimit(500000)

def search(x, y, z):
    if y >= H or x >= W or x < 0 or y <  0:
        return
    elif C[y][x] == z:
        return
    elif itta[y][x] != 0:
        return
    else:
        itta[y][x] = 0.00000001 # appendすると遅くなる
        prez = C[y][x]
        if C[y][x] == '.':
            itta[y][x] = 1
    
    search(x+1, y, prez)
    search(x-1, y, prez)
    search(x, y+1, prez)
    search(x, y-1, prez) 

ans = 0
# #を探しに行く
for y in range(H):
    for x in range(W):
        if C[y][x] != '#':
            pass
        else:
            itta = [[0] * W for i in range(H)]
            search(x, y, '.')
            ans += int(sum(map(sum, itta))) 
            # 入れ子リスト（２次元配列）の合計値
            # https://maku77.github.io/python/numstr/sum.html

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
C = [input() for i in range(H)]

import sys
sys.setrecursionlimit(500000)

itta = [[0] * W for i in range(H)]

def search(x, y, z):
    if y >= H or x >= W or x < 0 or y <  0:
        return
    elif C[y][x] == z:
        return
    elif itta[y][x] == 1:
        return
    elif C[y][x] == z:
        return
    else:
        itta[y][x] = 1
        
        if C[y][x] == '.':
            bw_count[0] += 1
        else:
            bw_count[1] += 1
        
        prez = C[y][x]
        
    search(x+1, y, prez)
    search(x-1, y, prez)
    search(x, y+1, prez)
    search(x, y-1, prez) 

ans = 0

for y in range(H):
    for x in range(W):
        if itta[y][x] ==1:
            pass
        else:
            bw_count = [0, 0]
            search(x, y, '-')
            
            ans += bw_count[0] * bw_count[1]  

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

MOD=10**9+7
import fractions
N=int(input())
if N==1:
  A=int(input())
  print(1)
  exit()
  
A=list(map(int, input().split()))

def f(a, b):
  return a*b//fractions.gcd(a, b)

tmp=f(A[0], A[1])
for i in range(2, N):
  tmp=f(tmp, A[i])
  
out=0
for i in range(N):
  out+=tmp//A[i]
  out%=MOD

print(out)

### FIXED CODE ###

MOD=10**9+7
import fractions
N=int(input())
if N==1:
  A=int(input())
  print(1)
  exit()

A=list(map(int, input().split()))
 
def f(a, b):
  return a*b//fractions.gcd(a, b)
 
if N>10:
  A1=A[:N//2]
  A2=A[N//2:]
  
  tmp1=f(A1[0], A1[1])
  n1=len(A1)
  for i in range(2, n1):
    tmp1=f(tmp1, A1[i])
    
  tmp2=f(A2[0], A2[1])
  n2=len(A2)
  for i in range(2, n2):
    tmp2=f(tmp2, A2[i])
    
  tmp=f(tmp1, tmp2)
  
  out1=sum([(tmp1//A1[i]) for i in range(n1)])
  out2=sum([(tmp2//A2[i]) for i in range(n2)])
  out1*=(tmp//tmp1)
  out2*=(tmp//tmp2)
  print((out1+out2)%MOD)
  exit()
  
tmp=f(A[0], A[1])
for i in range(2, N):
  tmp=f(tmp, A[i])
out=0
print(sum([(tmp//A[i])%MOD for i in range(N)])%MOD)
### BUGGY CODE ###

from bisect import bisect_left,bisect_right
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

num=[0]*30
for i in range(30):
    t = pow(2,i)
    K=(i%(2*t) for i in A)
    L=sorted(i%(2*t) for i in B)
    #L=sort()
    #print(K,L)
    a = 0
    for k in K:
        x = bisect_left(L,2*t-k)-bisect_left(L,t-k)
        y = bisect_left(L,4*t-k)-bisect_left(L,3*t-k)
        #print(x,y)
        a =(a+x+y)%2
    num[i]=a
ans =0
s=1
for z in num:
    ans += z*s
    s*=2
print(ans)



### FIXED CODE ###

from bisect import bisect_left,bisect_right
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

num=[0]*30
for i in range(30):
    t = pow(2,i)
    K=sorted(i%(2*t) for i in A)
    L=sorted(i%(2*t) for i in B)
    #L=sort()
    #print(K,L)
    a = 0
    #尺取り法,i*tより小さい整数を数える
    S=[i*t for i in range(1,5)]
    count=[N]*4
    for k in K:
        for j in range(4):
            while L[count[j]-1]+k>=S[j] and count[j]>0:
                count[j]-=1
        a +=count[3]-count[2]+count[1]-count[0]
        #print(count,a)
    num[i]=a%2
ans =0
s=1
for z in num:
    ans += z*s
    s*=2
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
P = 0
A_l = [num% (10**9+7) for num in A]
 
for i in range(N):
  sum=0
  for j in range(i+1,N):
    sum += A_l[j]
  P += A_l[i]*sum
    
ans = P%(10**9+7)
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
P = 0
S = sum(A)
m = 10**9+7

for i in range(N):
  S -= A[i]
  P += A[i]*S
  
ans = P%m
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
k_list=[]

for i in range(k):
    l,r=map(int,input().split())
    k_list.append([l,r])

dp=[0]*n
dp[0]=1
dpsum=[0]*n
dpsum[0]=1

for i in range(1,n):
    for j in range(k):
        l,r=k_list[j]
        li=i-r
        ri=i-l
        if ri<0:
            continue
        if li<=0:
            dp[i]+=dpsum[ri]
        else:
            dp[i]+=dpsum[ri]-dpsum[li-1]
    dpsum[i]=dpsum[i-1]+dp[i]

print(dp[n-1]%998244353)


### FIXED CODE ###

n,k=map(int,input().split())
k_list=[]

for i in range(k):
    l,r=map(int,input().split())
    k_list.append([l,r])

dp=[0]*(n+1)
dp[1]=1
dpsum=[0]*(n+1)
dpsum[1]=1

for i in range(1,n):
    dpsum[i]=dp[i]+dpsum[i-1]
    for j in range(k):
        l,r=k_list[j]
        li=i+l
        ri=i+r+1
        if li<=n:
            dp[li]+=dpsum[i]
            dp[li]=dp[li]%998244353
        if ri<=n:
            dp[ri]-=dpsum[i]
            dp[ri]=dp[ri]%998244353

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

x,y,z,k = map(int,input().split())
a_list = list(map(int,input().split()))
b_list = list(map(int,input().split()))
c_list = list(map(int,input().split()))
a_list.sort(reverse = True)
b_list.sort(reverse = True)
c_list.sort(reverse = True)
def check(p):
  count = 0
  for i in range(x):
    for j in range(y):
      for m in range(z):
        if a_list[i] + b_list[j] + c_list[m] < p:
          break
        count += 1
        if count >= k:
          return True
  return False

left = 1
right = 10**20
while right - left > 1:
  middle = (right + left)//2
  if check(middle) == True:
    left = middle
  else:
    right = middle
ans_list = []
for i in range(x):
    for j in range(y):
      for m in range(z):
        if a_list[i] + b_list[j] + c_list[m] < left -1:
          break
        if a_list[i] + b_list[j] + c_list[m] >= left+1:
          ans_list.append(a_list[i] + b_list[j] + c_list[m])
nokori = k - len(ans_list)
for i in range(nokori):
  ans_list.append(left)
  
ans_list.sort(reverse = True)
for ans in ans_list:
  print(ans)
          


### FIXED CODE ###

x,y,z,k = map(int,input().split())
a_list = list(map(int,input().split()))
b_list = list(map(int,input().split()))
c_list = list(map(int,input().split()))
a_list.sort(reverse = True)
b_list.sort(reverse = True)
c_list.sort(reverse = True)
def check(p):
  count = 0
  for i in range(x):
    for j in range(y):
      for m in range(z):
        if a_list[i] + b_list[j] + c_list[m] < p:
          break
        count += 1
        if count >= k:
          return True
  return False

left = 1
right = 10**20
while right - left > 1:
  middle = (right + left)//2
  if check(middle) == True:
    left = middle
  else:
    right = middle
ans_list = []
for i in range(x):
    for j in range(y):
      for m in range(z):
        if a_list[i] + b_list[j] + c_list[m] < left +1:
          break
        elif a_list[i] + b_list[j] + c_list[m] >= left+1:
          ans_list.append(a_list[i] + b_list[j] + c_list[m])
nokori = k - len(ans_list)
for i in range(nokori):
  ans_list.append(left)
  
ans_list.sort(reverse = True)
for ans in ans_list:
  print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
import bisect

n, d, a = [int(item) for item in input().split()]
places = []
xh = []
for i in range(n):
    x, h = [int(item) for item in input().split()]
    xh.append((x, h))
    places.append(x)
xh.sort()
places.sort()

N = 2**((n - 1).bit_length())
data0 = [0]*(N+1)
data1 = [0]*(N+1)
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def _get(data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

ans = 0
for i, (x, h) in enumerate(xh):
    init_damage = (query(1, i+2) - query(1, i+1)) * a
    if init_damage >= h:
        continue
    bomb = (h - init_damage + a - 1) // a
    ans += bomb
    r_lim = bisect.bisect_right(places, x+2*d)
    add(1, r_lim+1, bomb)
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
import bisect

n, d, a = [int(item) for item in input().split()]
places = []
xh = []
for i in range(n):
    x, h = [int(item) for item in input().split()]
    xh.append((x, h))
    places.append(x)
xh.sort()
places.sort()

N = 2**((n - 1).bit_length())
data0 = [0]*(N+1)
data1 = [0]*(N+1)
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def _get(data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

ans = 0
for i, (x, h) in enumerate(xh):
    init_damage = (query(1, i+2) - query(1, i+1)) * a
    if init_damage >= h:
        continue
    bomb = (h - init_damage + a - 1) // a
    ans += bomb
    r_lim = bisect.bisect_right(places, x+2*d)
    add(1, r_lim+1, bomb)
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict


def solve():
  ## input
  N = int(input())
  An = [[i-1 for i in list(map(int, input().split()))] for _ in range(N)]  

  ## solve
  ret = 0
  Pn = [0 for _ in range(N)]
  while min(Pn) < N-1:
    dct = defaultdict(lambda:set([]))
    game = 0
    for i in range(N):
      if Pn[i] >= N-1:
        continue
      else:
        j = An[i][Pn[i]]
        if i in dct[j]:
          dct[j].remove(i)
          game += 1
          Pn[i] += 1
          Pn[j] += 1
        else:
          dct[i].add(j)
    if game > 0:
      ret += 1
    else:
      return -1
  return ret

print(solve())


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import deque,defaultdict
from sys import stdin



def solve():
  ## input
  N = int(input())
  An = [deque([i-1 for i in list(map(int, stdin.readline().rstrip().split()))]) for _ in range(N)]

  ## solve
  Pn = set([i for i in range(N)])
  count = 0
  while len(Pn) > 0:
    Qn = set([])
    dct = defaultdict(lambda:set([]))
    for i in Pn:
      j = An[i][0]
      if i in dct[j]:
        An[i].popleft()
        if len(An[i]) > 0:
          Qn.add(i)
          Qn.add(An[i][0])
        An[j].popleft()
        if len(An[j]) > 0:
          Qn.add(j)
          Qn.add(An[j][0])
      else:
        dct[i].add(j)
    Pn = Qn
    count += 1
  for i in range(N):
    if len(An[i]) > 0:
      return -1
  return count



print(solve())
### BUGGY CODE ###

from itertools import product
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    can_open.append(sum(1 << (c-1) for c in map(int, input().split())))

n_bit = 1 << n
INF = 10**18
dp = [INF]*n_bit
dp[0] = 0

for j, (x, y) in product(range(n_bit), zip(can_open, cost)):
    m = j | x
    dp[m] = min(dp[m], dp[j]+y)

print(dp[-1] if dp[-1] != INF else -1)

### FIXED CODE ###

n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    it = map(int, input().split())
    x = 0
    for c in it:
        x += 1 << (c-1)
    can_open.append(x)

n_bit = 1 << n
INF = 10**18
dp = [[INF]*n_bit for _ in range(m+1)]
dp[0][0] = 0

# 配る
for i in range(m):
    for j in range(n_bit):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

        if (j | can_open[i]) <= n_bit:
            dp[i+1][j | can_open[i]
                    ] = min(dp[i+1][j | can_open[i]], dp[i+1][j]+cost[i])

print(dp[-1][-1] if dp[-1][-1] != INF else -1)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
score = 1
for i in range(k):
    score *= a[i]

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

### FIXED CODE ###

n, k = map(int, input().split())
a = 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 = list(map(int, input().split()))
f = 0
for i in range(len(A)):
    check = False
    for j in range(len(A)):
        if i == j:
            continue
        else:
            if A[i] % A[j] == 0:
                check = True
                break
    if check == True:
        f += 1
ans = len(A) - f
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
S = set(A)
M = max(S)
A.sort()

pre_a = 0
for a in A:
    if a == pre_a:
        S.discard(a)
    if a in S:
        j = a * 2
        while j <= M:
            S.discard(j)
            j += a
    pre_a = a
print(len(S))
### BUGGY CODE ###

N,M = map(int,input().split(" "))
list = []
for i in range(N):
    A,B = map(int,input().split(" "))
    list.append([A,B])
#print(list)
list = sorted(list)
#print(list)
cost = 0
while True:
    #print(cost)
    M -= list[0][1]
    if M <= 0:
        cost += list[0][0] * (list[0][1]+M)
        break
    else:
        cost += list[0][0] * list[0][1]
        list.remove(list[0])
print(cost)


### FIXED CODE ###

N,M = map(int,input().split(" "))
list = []
for i in range(N):
    A,B = map(int,input().split(" "))
    list.append([A,B])
#print(list)
list = sorted(list)
#print(list)
cost = 0
while True:
    #print(cost)
    M -= list[0][1]
    if M <= 0:
        cost += list[0][0] * (list[0][1]+M)
        break
    else:
        cost += list[0][0] * list[0][1]
        list.remove(list[0])
print(cost)