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

# 区間[i,j]における最小値を返す
# 値の更新をする
import fractions
class segment_tree:
    '''
    init_val(int): 初期化値
    Input(array):  入力
    '''
    def __init__(self, init_val, Input):
        #self.num:n以上の最小の2のべき乗(一番下のNodeの数)
        n=len(Input)
        self.init_val = init_val
        self.num = 2 ** (n - 1).bit_length()
        self.seg = [init_val] * 2 * self.num
        for i in range(n):
            self.seg[i + self.num - 1] = Input[i]
        for i in range(self.num - 2, -1, -1):
            self.seg[i]=self._segfunc(self.seg[2*i+1],self.seg[2*i+2])
    def _segfunc(self, left, right):
        '''
        ここに求めたい関数を入れる
        ex)最小値問題→min, 
        left:左の子
        right:右の子
        '''
        res=fractions.gcd(left,right)
        return res
    def update(self, k, x):
        '''
        k番目の値をxに書き換える
        '''
        k += self.num - 1
        self.seg[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.seg[k] = self._segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])
    def query(self, p, q):
        '''
        区間[p,q)の目的の値を取り出す
        '''
        if q <= p:
            return self.init_val
        p += self.num - 1
        q += self.num - 2
        res = self.init_val
        while q - p > 1:
            if p % 2 == 0: #始点が偶数or終点が奇数だと端っこが余る
                res = self._segfunc(res, self.seg[p])
            if q % 2 == 1:
                res = self._segfunc(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        res = self._segfunc(res, self.seg[p])
        res = self._segfunc(res, self.seg[q])
        return res
INF = 10 ** 10
n=int(input())
a=list(map(int,input().split()))

# a = [randint(0,N*2) for _ in range(N)]
dp = segment_tree(0, a)
ans=-1
for i in range(n):
  ans=max(ans,fractions.gcd(dp.query(0,i),dp.query(i+1,n)))
print(ans)

### FIXED CODE ###

def gcd(x, y):
  if y == 0:
    return x
  else:
    return gcd(y, x % y) #再帰定義
n=int(input())
a=list(map(int,input().split()))
l=[0]*n
r=[0]*n
for i in range(1,n):
  if i==1:
    l[1]=a[0]
    r[-2]=a[-1]
  else:
    l[i]=gcd(l[i-1],a[i-1])
    r[-i-1]=gcd(r[-i],a[-i])
g=[0]*n
for i in range(n):
  if l[i]==0 or r[i]==0:
    g[i]=l[i]+r[i]
  else:
    g[i]=gcd(l[i],r[i])
print(max(g))
### BUGGY CODE ###

a,b,c,d = map(int,input().split())
e = 0

for i in range(a,b+1):
  if i % c == 0 or i % d == 0:
    continue
  else:
    e += 1
print(e)

### FIXED CODE ###

import fractions

a,b,c,d = map(int,input().split())
lcm = c * d // fractions.gcd(c,d)

cde = b // c - (a - 1) // c
dde = b // d - (a - 1)  // d
lde = b // lcm - (a - 1)  // lcm

print(b - a + 1 - cde - dde + lde)
### BUGGY CODE ###

from itertools import permutations

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

N,M,R=[int(x) for x in input().split()]
r=[int(x)-1 for x in input().split()]

INF = float("inf")
route_list=[[INF]*N for _ in range(N)]

for i in range(M):
    a,b,c=[int(x) for x in input().split()]
    route_list[a-1][b-1]=c
    route_list[b-1][a-1]=c

wa_list=warshall_floyd(route_list)
ans=30**9

for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)

### FIXED CODE ###

import math
from itertools import permutations

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

N,M,R=[int(x) for x in input().split()]
r=[int(x)-1 for x in input().split()]

route_list=[[10**9]*N for i in range(N)]

for i in range(M):
    a,b,c=[int(x) for x in input().split()]
    route_list[a-1][b-1]=c
    route_list[b-1][a-1]=c

wa_list=warshall_floyd(route_list)
ans=30**9

for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

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

import sys
readline = sys.stdin.readline

from heapq import heappop as hpp, heappush as hp
def dijkstra(N, s, Edge):
    inf = geta
    dist = [inf] * N
    dist[s] = 0
    Q = [s]
    dp = [0]*N
    dp[s] = 1
    while Q:
        k = hpp(Q)
        dn, vn = divmod(k, geta)
        if dn > dist[vn]:
            continue
        for k in Edge[vn]:
            df, vf = divmod(k, geta)
            if dist[vn] + df < dist[vf]:
                dist[vf] = dist[vn] + df
                dp[vf] = dp[vn]
                hp(Q, ((dn + df)*geta)+vf)
            elif dist[vn] + df == dist[vf]:
                dp[vf] = (dp[vf] + dp[vn]) % MOD
    return dist, dp

MOD = 10**9+7
N, M = map(int, readline().split())
S, T = map(int, readline().split())
S -= 1
T -= 1

geta = 10**15
Edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, d = map(int, readline().split())
    u -= 1
    v -= 1
    Edge[u].append(d*geta+v)
    Edge[v].append(d*geta+u)
    

dists, dps = dijkstra(N, S, Edge)
distt, dpt = dijkstra(N, T, Edge)
st = dists[T]

onpath = [i for i in range(N) if dists[i] + distt[i] == st]

ans = dps[T]**2%MOD
for i in onpath:
    if 2*dists[i] == 2*distt[i] == st:
        ans = (ans - pow(dps[i]*dpt[i], 2, MOD))%MOD
    
    for k in Edge[i]:
        cost, vf = divmod(k, geta)
        if dists[i] + cost + distt[vf] == st:
            if 2*dists[i] < st < 2*dists[vf]:
                ans = (ans - pow(dps[i]*dpt[vf], 2, MOD))%MOD
print(ans)


### FIXED CODE ###

import sys
readline = sys.stdin.readline

from heapq import heappop as hpp, heappush as hp
def dijkstra(N, s, Edge):
    inf = geta
    dist = [inf] * N
    dist[s] = 0
    Q = [(0, s)]
    dp = [0]*N
    dp[s] = 1
    while Q:
        dn, vn = hpp(Q)
        if dn > dist[vn]:
            continue
        for df, vf in Edge[vn]:
            if dist[vn] + df < dist[vf]:
                dist[vf] = dist[vn] + df
                dp[vf] = dp[vn]
                hp(Q, (dn + df,vf))
            elif dist[vn] + df == dist[vf]:
                dp[vf] = (dp[vf] + dp[vn]) % MOD
    return dist, dp

MOD = 10**9+7
N, M = map(int, readline().split())
S, T = map(int, readline().split())
S -= 1
T -= 1

geta = 10**15
Edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, d = map(int, readline().split())
    u -= 1
    v -= 1
    Edge[u].append((d, v))
    Edge[v].append((d, u))
    

dists, dps = dijkstra(N, S, Edge)
distt, dpt = dijkstra(N, T, Edge)
st = dists[T]

onpath = [i for i in range(N) if dists[i] + distt[i] == st]

ans = dps[T]**2%MOD
for i in onpath:
    if 2*dists[i] == 2*distt[i] == st:
        ans = (ans - pow(dps[i]*dpt[i], 2, MOD))%MOD
    
    for cost, vf in Edge[i]:
        if dists[i] + cost + distt[vf] == st:
            if 2*dists[i] < st < 2*dists[vf]:
                ans = (ans - pow(dps[i]*dpt[vf], 2, MOD))%MOD
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M_a: int, M_b: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    t = [[float("inf")] * (10 * N + 1) for _ in range(10 * N + 1)]
    t[0][0] = 0
    for ai, bi, ci in zip(a, b, c):
        for ta in reversed(range(ai, len(t))):
            for tb in reversed(range(bi, len(t[0]))):
                t[ta][tb] = min(t[ta][tb], t[ta - ai][tb - bi] + ci)
    ans = min(
        t[k * M_a][k * M_b]
        for k in range(1, min((len(t) - 1) // M_a, (len(t[0]) - 1) // M_b) + 1)
    )
    print(-1 if ans == float("inf") else ans)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M_a = int(next(tokens))  # type: int
    M_b = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]"
    b = [int()] * (N)  # type: "List[int]"
    c = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M_a, M_b, a, b, c)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
def solve():
    N, M_a, M_b = [int(x) for x in input().split()]
    inf = 100000
    t = [[inf] * (10 * N + 1) for _ in range(10 * N + 1)]
    t[0][0] = 0
    for _ in range(N):
        ai, bi, ci = [int(x) for x in input().split()]
        for ta in reversed(range(ai, len(t))):
            for tb in reversed(range(bi, len(t[0]))):
                t[ta][tb] = min(t[ta][tb], t[ta - ai][tb - bi] + ci)
    ans = min(
        t[k * M_a][k * M_b]
        for k in range(1, min((len(t) - 1) // M_a, (len(t[0]) - 1) // M_b) + 1)
    )
    print(-1 if ans >= inf else ans)


solve()
### BUGGY CODE ###

from math import floor

a, b, n = map(int, input().split())
# a, b, n = 4628, 3261783, 3421

max_num = -99999999999999999999999

for i in range(n):
    x = i + 1
    num = floor(a*x / b) - a * floor(x / b)
    
    if num > max_num:
        max_num = num
        
print(max_num)

### FIXED CODE ###

from math import floor

a, b, n = map(int, input().split())
        
x = min(n, b-1)
if x < 0:
    x = 0
    
print(floor(a*x / b) - a * floor(x / b))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
count=0
while len(a)>=2:
    ma=max(a)
    guess =a.index(ma)
    for i in range(guess+1,len(a)):
        count+=ma-a[i]
    a=a[:guess]
print(count)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
count=0
ma=a[0]
for i in range(1,len(a)):
    if a[i]<ma:
        count+=ma-a[i]
    else:
        ma=a[i]
print(count)
### BUGGY CODE ###

H,W=map(int,input().split())
hlen = list(map(int,input().split()))
wlen =	list(map(int,input().split()))
hlen.sort(reverse=True)
wlen.sort(reverse=True)
hhlen =[0 for _ in range(H*W+1)]
wwlen =[0 for _ in range(H*W+1)]
for x,xx in zip([hlen,wlen],[hhlen,wwlen]):
	c = 1
	for y in x:
		if xx[y] != 0:
			print(0)
			exit()
		else:
			xx[y] = c


def Count(x,l):
	ret = 0
	while l[ret] > x :
		ret += 1
		if ret == len(l):
			break
	return ret	

m = max(hlen[0],wlen[0])
count = 1
for num in range(1,H*W+1)[::-1]:
	if hhlen[num] and wwlen[num]:
		count *= 1
	elif hhlen[num]:
		count *= Count(num,wlen)
	elif wwlen[num]:
		count *= Count(num,hlen)
	else:
		count *= Count(num,hlen)*Count(num,wlen) - (m-num)
	#print(num,flagh,flagw,count)
	count %= (10**9+7)
print(count % (10**9+7))

### FIXED CODE ###

H,W=map(int,input().split())
hlen = list(map(int,input().split()))
wlen =	list(map(int,input().split()))
hlen.sort(reverse=True)
wlen.sort(reverse=True)
hlen.append(0)
wlen.append(0)

m = H*W
count = 1
h=0
w=0
for num in range(1,H*W+1)[::-1]:
	if hlen[h] == num and wlen[w] == num:
		count *= 1
		h += 1
		w += 1
	elif hlen[h] == num:
		count *= w
		h += 1
	elif wlen[w] == num:
		count *= h
		w += 1
	else:
		count *= h*w - (m-num)
	#print(num,flagh,flagw,count)
	count %= (10**9+7)
print(count)
### BUGGY CODE ###

import math

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

keys = []

for i in range(M):
    a, b = list(map(int, input().split()))
    key_bit = 0
    c = list(map(int, input().split()))
    for j in range(b):
        key_bit |= 1 << (c[j] - 1)
    keys.append([a, key_bit])

dp = [[math.inf]*(1 << N) for _ in range(M + 1)]

dp[0][0] = 0

for i in range(M):
    for j in range(1 << N):
        dp[i + 1][j] = dp[i][j]
        for k in range(1 << N):
            if k | keys[i][1] == j:
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][k] + keys[i][0])

if dp[M][-1] == math.inf:
    print(-1)
else:
    print(dp[M][-1])


### FIXED CODE ###

import math

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

keys = []

for i in range(M):
    a, b = list(map(int, input().split()))
    key_bit = 0
    c = list(map(int, input().split()))
    for j in range(b):
        key_bit |= 1 << (c[j] - 1)
    keys.append([a, key_bit])

dp = [math.inf]*(1 << N)

dp[0] = 0

for i in range(M):
    for j in range(1 << N):
        dp[j | keys[i][1]] = min(dp[j | keys[i][1]], dp[j] + keys[i][0])

if dp[-1] == math.inf:
    dp[-1] = -1

print(dp[-1])
### BUGGY CODE ###

#G
import pprint
H,W,K=map(int,input().split())
import copy
x1,y1,x2,y2=map(int,input().split())
#raw=["#"]+["."]*(601)+["#"]
lastraw=["@"]*(W+2)
field=[["@"]*(W+2)]
for i in range(H):
  field.append(["@"]+list(input())+["@"])

field.append(lastraw)

#print(field)

goal_point=(y2,x2)

[sy,sx]=[y1,x1]
[gy,gx]=[y2,x2]

field[x1][y1]=0
queue=[[sy,sx]]
tests = ((-1,0),(0, 1),(1, 0),(0, -1))
moves=0

while True:
  if len(queue)==0:
    moves=-1
    break
  queue_next = []
  moves += 1
  #pprint.pprint(field)
  for y, x in queue:
    for ny, nx in tests:
      ty, tx = y + ny, x + nx
      if field[tx][ty] == '.' or field[tx][ty] ==moves:
        field[tx][ty] = moves
        queue_next.append((ty, tx))
        #print(ty,tx)
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            #print(ty,tx)
          elif field[tx][ty] ==moves:
            pass
          else:
            break
      elif field[tx][ty] ==moves:
        #field[tx][ty] = moves
        #queue_next.append((ty, tx))
        #print(ty,tx)
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            #print(ty,tx)
          elif field[tx][ty] ==moves:
            pass
          else:
            break
  queue = queue_next
  if goal_point in queue:
    break
#pprint.pprint(field)
print(moves)

### FIXED CODE ###

#G
import pprint
H,W,K=map(int,input().split())
import copy
x1,y1,x2,y2=map(int,input().split())
#raw=["#"]+["."]*(601)+["#"]
lastraw=["@"]*(W+2)
field=[["@"]*(W+2)]
for i in range(H):
  field.append(["@"]+list(input())+["@"])

field.append(lastraw)

#print(field)

goal_point=(y2,x2)

[sy,sx]=[y1,x1]
[gy,gx]=[y2,x2]

field[x1][y1]=0
queue=[[sy,sx]]
tests = ((-1,0),(0, 1),(1, 0),(0, -1))
moves=0

while True:
  if len(queue)==0:
    moves=-1
    break
  queue_next = []
  moves += 1
  #pprint.pprint(field)
  for y, x in queue:
    for ny, nx in tests:
      ty, tx = y + ny, x + nx
      if field[tx][ty] == '.':
        field[tx][ty] = moves
        queue_next.append((ty, tx))
        #print(ty,tx)
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            #print(ty,tx)
          elif field[tx][ty] ==moves:
            pass
          else:
            break
      elif field[tx][ty] ==moves:
        #field[tx][ty] = moves
        #queue_next.append((ty, tx))
        #print(ty,tx)
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            #print(ty,tx)
          elif field[tx][ty] ==moves:
            pass
          else:
            break
  queue = queue_next
  if goal_point in queue:
    break
#pprint.pprint(field)
print(moves)
### BUGGY CODE ###

N = int(input())

a_list = []

b_list = []

for i in range(N):
    a,b = map(int,input().split())
    a_list.append(a)
    b_list.append(b)

a_list = a_list[::-1]
b_list = b_list[::-1]

#print(a_list)
#print(b_list)

st = 0

for i in range(N):
    a_list[i] += st
    if a_list[i] % b_list[i]:
        if a_list[i] < b_list[i]:
            st += b_list[i]-a_list[i]
        elif a_list[i] > b_list[i]:
            n = b_list[i]
            j = 2
            while a_list[i] > n:
                n = b_list[i]*j
                j += 1
            st += n-a_list[i]
print(st)

### FIXED CODE ###

N = int(input())

a_list = []

b_list = []

for i in range(N):
    a,b = map(int,input().split())
    a_list.append(a)
    b_list.append(b)

a_list = a_list[::-1]
b_list = b_list[::-1]

#print(a_list)
#print(b_list)

st = 0

for i in range(N):
    a_list[i] += st
    if a_list[i] % b_list[i]:
        if a_list[i] < b_list[i]:
            st += b_list[i]-a_list[i]
        elif a_list[i] > b_list[i]:
            st += b_list[i]*((a_list[i]//b_list[i])+1)-a_list[i]
print(st)
### BUGGY CODE ###

import math
 
d,g = [int(i) for i in input().split()]
P = []
C = []
for i in range(d):
    p,c = [int(i) for i in input().split()]
    P.append(p)
    C.append(c)

# cnt = 0
# def count():
#     global cnt
#     cnt+=1
#     print(cnt)

def flag(point,P,now):
    if point+100*(now+1)*P >= g: return 1
    else: return 0

m = 10**9
def score(point = 0, n = 0, now=-1, done=[]):
    global m
    if m <= n: return
    elif point >= g: m = n
    elif flag(point,P[now],now):
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: m = n
    else:
        done.append(now)
        if now == -1:
            for i in range(d):
                score(point, n, i, done[:])
        elif m <= n+P[now]: return
        else:
            for i in range(d):
                if not i in done:
                    score(point+P[now]*100*(now+1) + C[now], n + P[now], i, done[:])

score()
print(m)

### FIXED CODE ###

import math
 
d,g = [int(i) for i in input().split()]
P = []
C = []
for i in range(d):
    p,c = [int(i) for i in input().split()]
    P.append(p)
    C.append(c)

# cnt = 0
# def count():
#     global cnt
#     cnt+=1
#     print(cnt)

def flag(point,P,now):
    if point+100*(now+1)*(P-1) >= g: return 1
    elif point+100*(now+1)*P + C[now] >= g: return 2
    else: return 0

m = 10**9
def score(point = 0, n = 0, now=-1, remain = list(range(d))):
    global m
    if m <= n: return
    elif now == -1:
        for i in remain:
            score(point, n, i, remain)
    elif point >= g: m = n
    elif flag(point,P[now],now) == 1:
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: m = n
    elif flag(point,P[now],now) == 2:
        n += P[now]
        if m > n: m = n
    else:
        if m <= n+P[now]: return
        else:
            remain = remain[:]
            remain.remove(now)
            nxtp = point + P[now]*100*(now+1) + C[now]
            for i in remain:
                score(nxtp, n + P[now], i, remain)

score()
print(m)
### BUGGY CODE ###

n = int(input())
_s = input()
q = int(input())
query = [input() for _ in range(q)]

def bitsum(_bit, i):
    s = 0
    while i > 0:
        s += _bit[i]
        i -= i & (-i)
    return s

def bitadd(_bit, i, x):
    while i <= n:
        _bit[i] += x
        i += i & (-i)
    return _bit

al = [chr(ord('a') + i) for i in range(26)]
al_to_idx = dict()
for i in range(26):
    al_to_idx[al[i]] = i

s = list(_s).copy()

# init
import math
n_ = int(math.log2(n)) + 1
bit = [[0] * (2 ** n_ + 1) for _ in range(26)]
for i in range(n):
    idx = al_to_idx[s[i]]
    bit[idx] = bitadd(bit[idx], i + 1, 1)
# print(bit)

for i in range(q):
    _query = query[i].split(' ')
    if _query[0] == '1':
        # decrement old
        idx = al_to_idx[s[int(_query[1]) - 1]]
        bit[idx] = bitadd(bit[idx], int(_query[1]), -1)

        s[int(_query[1]) - 1] = _query[2]
        # print(s)

        # increment
        idx = al_to_idx[_query[2]]
        bit[idx] = bitadd(bit[idx], int(_query[1]), 1)

    else:
        _ans = 0
        for idx in range(26):
            _bit = bit[idx]
            c = bitsum(_bit, int(_query[2])) - bitsum(_bit, int(_query[1]) - 1)
            if c != 0:
                _ans += 1
        print(_ans)


### FIXED CODE ###

n = int(input())
_s = input()
q = int(input())
query = [input() for _ in range(q)]

def bitsum(_bit, i):
    s = 0
    while i > 0:
        s += _bit[i]
        i -= i & (-i)
    return s

def bitadd(_bit, i, x):
    while i <= n:
        _bit[i] += x
        i += i & (-i)
    return _bit

al = [chr(ord('a') + i) for i in range(26)]
al_to_idx = dict()
for i in range(26):
    al_to_idx[al[i]] = i

s = list(_s)

# init
import math
n_ = int(math.log(n) / math.log(2)) + 1
bit = [[0] * (2 ** n_ + 1) for _ in range(26)]
for i in range(n):
    idx = al_to_idx[s[i]]
    bit[idx] = bitadd(bit[idx], i + 1, 1)
# print(bit)

for i in range(q):
    _query = query[i].split(' ')
    if _query[0] == '1':
        # decrement old
        idx = al_to_idx[s[int(_query[1]) - 1]]
        bit[idx] = bitadd(bit[idx], int(_query[1]), -1)

        s[int(_query[1]) - 1] = _query[2]
        # print(s)

        # increment
        idx = al_to_idx[_query[2]]
        bit[idx] = bitadd(bit[idx], int(_query[1]), 1)

    else:
        _ans = 0
        for idx in range(26):
            _bit = bit[idx]
            c = bitsum(_bit, int(_query[2])) - bitsum(_bit, int(_query[1]) - 1)
            if c != 0:
                _ans += 1
        print(_ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n,k = map(int,input().split())
sl = [0]*n
tree = [[] for i in range(n)]
mod = 10**9+7
q = []
ans = k

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

def perm(n, k = 1):
  pdt = 1
  if n != int(n) or k != int(k):
    raise ValueError("perm() not defined for float object")
  elif k < 0:
    pdt = 0
  elif n < 0:
    pdt = 0
  else:
    for x in range(n, n-k, -1):
      pdt *= x
  return pdt

if len(tree[0]) > 0:
  q = tree[0]
  ans = k*perm(k-1,len(tree[0]))%mod
  sl[0] = 1
else:
  print(k)
  exit()
  
while q:
  pos = q.pop(0)
  sl[pos] = 1
  lent = len(tree[pos]) - 1
  if lent > 0:
    ans = ans*perm(k-2,lent)%mod
  for i in tree[pos]:
    if sl[i] == 0:
      q.append(i)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
mod = 10**9+7

def main():
  
  n,k = map(int,input().split())
  sl = [0]*(n+1)
  tree = [[] for i in range(n+1)]
  
  for i in range(n-1):
    a,b = map(int,input().split())
    tree[a] += (b,)
    tree[b] += (a,)

  def dfs(x,depth,k):
    sl[x] = 1
    child = 0
    ans = 1
    for i in tree[x]:
      if sl[i] == 0:
        ans *= dfs(i,depth+1,k)
        child += 1
    if depth == 0:
      for x in range(k-1, k-1-child, -1):
        ans = ans * x % mod   
    else:    
      for x in range(k-2, k-2-child, -1):
        ans = ans * x % mod
    ans %= mod
    return ans

  print(dfs(1,0,k)*k%mod)

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

N, M = map(int, input().split())
drink = []
cost = 0
count = 0
d_count = 0
rest = 0


for _ in range(N):
    Drink = list(map(int, input().split()))
    drink.append(Drink)
    drink.sort()

for i in range(N):
    cost += drink[i][0] * drink[i][1]
    d_count += drink[i][1]
    count += 1
    if d_count > M:
      break
      
cost -= drink[count-1][0] * drink[count-1][1]
d_count -= drink[count-1][1]
rest = M - d_count
cost += rest * drink[count-1][0]
print(cost)
    


### FIXED CODE ###

N, M = map(int, input().split())
drink = []
cost = 0
d_count = 0


for _ in range(N):
    drink.append(list(map(int, input().split())))
    
drink = sorted(drink)

for i in range(N):
    cost += drink[i][0] * drink[i][1]
    d_count += drink[i][1] 
    if d_count > M:
      cost -= drink[i][0] * (d_count - M)
      break
      

print(cost)