Harryxun/stf_run huggingface dataset:
S = input()

MOD = 10**9+7

dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]


dp[0][0] = 1



for index in range(1, len(S) + 1):
    s = S[len(S) - index ]
    if s == '?':
	for i in range(10):
	    for pre_index in range(13):
                next_i = (i   +  pre_index * 10 ) % 13
                dp[index][next_i] += dp[index - 1][pre_index] % MOD
    else:
        i = int(s)
        for pre_index in range(13):
            next_i = (i +  pre_index * 10 ) % 13
            dp[index][next_i] += dp[index - 1][pre_index] % MOD




print(dp[len(S)][5] % MOD)



### FIXED CODE ###

S = input()
 
MOD = 10**9+7
 
dp = [[0]*13 for _ in range(len(S) + 1)]
 
 
dp[0][0] = 1
 
for index in range(len(S)):
    if S[index] == '?':
        for pre_index in range(13):
            for i in range(10):
                next_i = (i +  pre_index * 10 ) % 13
                dp[index+1][next_i] += dp[index][pre_index] 
                dp[index+1][next_i] %= MOD

    else:
        for pre_index in range(13):
            i = int(S[index])
            next_i = (i +  pre_index  * 10) % 13
            dp[index+1][next_i] += dp[index][pre_index] 
            dp[index+1][next_i] %= MOD
 
 
 
print(dp[len(S)][5])
n, d, a = map(int, input().split())
monster = []
for _ in range(n):
  x, h = map(int, input().split())
  monster.append((x, h))
monster.sort()
bomb = 0
j = 0
for i in range(n):
  while monster[j][0] - monster[i][0] <= 2 * d and j < n:
    j += 1
  if monster[i][1] <= 0:
    continue
  b = (monster[i][1] - 1) // a + 1
  atk = a * b
  bomb += b
  for k in range(i+1, j):
    monster[k][1] -= atk
print(bomb)

### FIXED CODE ###

import heapq
from collections import deque

n, d, a = map(int, input().split())
monster = []
for _ in range(n):
  x, h = map(int, input().split())
  heapq.heappush(monster, (x, h))
bomb = 0
damage = 0
queue = deque()
while monster:
  x, h = heapq.heappop(monster)
  while True:
    if queue and x > queue[0][0]:
      damage -= queue.popleft()[1]
    else:
      break
  h -= damage
  if h <= 0:
    continue
  b = (h - 1) // a + 1
  bomb += b
  queue.append((x + 2 * d, a * b))
  damage += a * b
print(bomb)
# list に入力を格納
list = list(map(int, input().split()))
# 小さい順に並び替え
list.sort()

if list[0] == 5 and list[1] == 5 and list[7] == 7:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

# list に入力を格納
list = list(map(int, input().split()))
# 小さい順に並び替え
list.sort()

if list[0] == 5 and list[1] == 5 and list[2] == 7:
    print('YES')
else:
    print('NO')
s,w = map(input().split(), int)
print("unsafe" if w >= s else "safe")

### FIXED CODE ###

s,w = map(int, input().split())
print("unsafe" if w >= s else "safe")
A, B, k = map(int, input().split())
lst = []
for i in range(1, 100):
  if A % i and B % i == 0:
    lst.append(i)
print(lst[-k])


### FIXED CODE ###

A, B, k = map(int, input().split())
lst = []
for i in range(1, 101):
  if A % i == 0 and B % i == 0:
    lst.append(i)
print(lst[-k])
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import defaultdict

def main():
    N, M = LI()
    edges = defaultdict(list)
    for _ in range(M):
        a, b = LI_()
        edges[a].append(b)
        edges[b].append(a)
    quads = []
    for i, e in enumerate(edges):
        c = len(e)
        if c % 2 == 1:
            loops = -1
            return 'No'
        if c >= 6:
            return 'Yes'
        if c == 4:
            quads.append(i)
    if len(quads) < 2:
        return 'No'
    for v in edges[quads[0]]:
        visited = [0] * N
        visited[quads[0]] = 1
        while v != quads[1]:
            visited[v] = 1
            for to in edges[v]:
                if visited[to] == 0:
                    v = to
                    break
            if visited[v] == 1:
                break
        if v != quads[1]:
            return 'Yes'

    return 'No'

print(main())

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import defaultdict, deque

def main():
    N, M = LI()
    edges = defaultdict(set)
    for _ in range(M):
        a, b = LI_()
        edges[a].add(b)
        edges[b].add(a)
    quads = set()
    sixes = 0
    for i, e in edges.items():
        c = len(e)
        if c % 2 == 1:
            return False
        if c >= 6:
            sixes += 1
        if c == 4:
            quads.add(i)
    if sixes > 0:
        return True
    if len(quads) > 2:
        return True
    if len(quads) < 2:
        return False
    s = quads.pop()
    t = quads.pop()
    for v0 in edges[s]:
        q = deque([v0])
        visited = {s, t}
        while len(q) > 0:
            v = q.pop()
            for to in edges[v]:
                if v != v0 and to == s:
                    return True
                if to not in visited:
                    q.append(to)
                    visited.add(to)

    return False

print('Yes' if main() else 'No')
import numpy as np
import math

n , k = list(map(int, input().split()))
kaijou = np.zeros((n + 1,k + 1))
def combi(a,b):
    if kaijou[a][b] == 0:
        kaijou[a][b] = math.factorial(a) / (math.factorial(b) * math.factorial(a-b))
    return kaijou[a][b]
i = 2
mod = 10 ** 9 + 7
for i in range(1, k + 1):
    if n - k + 1 >= i and k - 1 >= i - 1:
        print(int(combi(n - k + 1,i) * combi(k - 1, i - 1) % mod))
    else:
        print(0)


### FIXED CODE ###

import numpy as np
import math

n , k = list(map(int, input().split()))
def combi(a,b):
    return  math.factorial(a) // (math.factorial(b) * math.factorial(a-b))
i = 2
mod = 10 ** 9 + 7
for i in range(1, k + 1):
    if n - k + 1 >= i and k - 1 >= i - 1:
        print(int(combi(n - k + 1,i) * combi(k - 1, i - 1) % mod))
    else:
        print(0)
import sys
sys.setrecursionlimit(10*9)

n,m,k = map(int,input().split())
parent_of = [-1 for _ in range(n)]
#print(parent_of)
def root_of(x):
	if parent_of[x] < 0:
		return x
	else:
		parent_of[x] = root_of(parent_of[x])
		return parent_of[x]

def unite(x,y):
	top_root_x = root_of(x)
	top_root_y = root_of(y)
	if top_root_x == top_root_y:
		return False
	if parent_of[top_root_x] > parent_of[top_root_y]:
		top_root_x,top_root_y = top_root_y,top_root_x
	#print(parent_of[top_root_y])
	parent_of[top_root_x] += parent_of[top_root_y]
	parent_of[top_root_y] = top_root_x
	return True

def size_of(x):
		return -parent_of[root_of(x)]

def is_same(x,y):
	return root_of(x) == root_of(y)

friend_list = [-1] * n
for _ in range(m):
	a,b = map(int,input().split())
	a -= 1
	b -= 1
	friend_list[a] -=1
	friend_list[b] -=1
	unite(a,b)

for _ in range(k):
	c,d = map(int,input().split())
	c -= 1
	d -= 1
	if root_of(c) == root_of(d):
		block_list[c] -= 1
		block_list[d] -= 1
for i in range(n):
	friend_list[i] += size_of(i)
	#print(size_of(i))
print(*friend_list)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10*9)

n,m,k = map(int,input().split())
parent_of = [-1 for _ in range(n)]
#print(parent_of)
def root_of(x):
	if parent_of[x] < 0:
		return x
	else:
		parent_of[x] = root_of(parent_of[x])
		return parent_of[x]

def unite(x,y):
	top_root_x = root_of(x)
	top_root_y = root_of(y)
	if top_root_x == top_root_y:
		return False
	if parent_of[top_root_x] > parent_of[top_root_y]:
		top_root_x,top_root_y = top_root_y,top_root_x
	#print(parent_of[top_root_y])
	parent_of[top_root_x] += parent_of[top_root_y]
	parent_of[top_root_y] = top_root_x
	return True

def size_of(x):
		return -parent_of[root_of(x)]

def is_same(x,y):
	return root_of(x) == root_of(y)

friend_list = [-1] * n
for _ in range(m):
	a,b = map(int,input().split())
	a -= 1
	b -= 1
	friend_list[a] -=1
	friend_list[b] -=1
	unite(a,b)

for _ in range(k):
	c,d = map(int,input().split())
	c -= 1
	d -= 1
	if root_of(c) == root_of(d):
		friend_list[c] -= 1
		friend_list[d] -= 1
for i in range(n):
	friend_list[i] += size_of(i)
	#print(size_of(i))
print(*friend_list)
A, B = map(int, input().split())
 
if A>=B:
  C = A%B
else:
  C = B%A
 
count = 0
 
now = 0
 
a = 2
 
while C >= a*a:
  if C%a == 0:
    if a != now:
      count += 1
      now = a
    C /= a
  else:
    a +=1
 
if C > 2 & C != now:
  count +=1
 
count += 1
 
print(count)

### FIXED CODE ###

A, B = map(int, input().split())


A_yaku = []

now = 0

a = 2

while A >= a*a:
  if A%a == 0:
    if a != now:
      A_yaku.append(a)
      now = a
    A /= a
  else:
    a +=1

if A != now and A != 1:
  A_yaku.append(A)

B_yaku = []

now = 0

a = 2

while B >= a*a:
  if B%a == 0:
    if a != now:
      B_yaku.append(a)
      now = a
    B /= a
  else:
    a +=1

if B != now and B != 1:
  B_yaku.append(B)

count = 0

if(len(A_yaku) >= len(B_yaku)):
  for i in range(0,len(B_yaku)):
    if(B_yaku[i] in A_yaku):
      count += 1
else:
  for i in range(0,len(A_yaku)):
    if(A_yaku[i] in B_yaku):
      count += 1

count += 1

print(count)
from heapq import heappush,heappop 
from math import sqrt
inf=float("inf")

xs,ys,xt,yt=map(int,input().split())
n=int(input())

q=[]
l=[(xs,ys,0),(xt,yt,0)]+[tuple(map(int,input().split())) for _ in range(n)]

sizeV=len(l)
rests={*range(sizeV)}
cost=[inf]*sizeV
cost[0]=0
heappush(q,(0,0))

while q:
  c1,i=heappop(q)
  if c1>cost[i]:continue

  rests.remove(i)
  if not rests:break

  xi,yi,ri=l[i]
  for j in rests:
    xj,yj,rj=l[j]
    d=max(0,sqrt((xj-xi)**2+(yj-yi)**2)-ri-rj)
    c2=c1+d
    if c2<cost[j]:
      cost[j]=c2
      heappush(q,(c2,j))

print(cost[1])

### FIXED CODE ###

from heapq import heappush,heappop 
from math import sqrt
inf=float("inf")

xs,ys,xt,yt=map(int,input().split())
n=int(input())

q=[]
l=[(xs,ys,0),(xt,yt,0)]+[tuple(map(int,input().split())) for _ in range(n)]

sizeV=len(l)
rests=set(range(sizeV))
cost=[inf]*sizeV
cost[0]=0
heappush(q,(0,0))

while q:
  c1,i=heappop(q)
  if c1>cost[i]:continue

  rests.remove(i)
  if not rests:break

  xi,yi,ri=l[i]
  for j in rests:
    xj,yj,rj=l[j]
    d=max(0.0,sqrt((xj-xi)**2+(yj-yi)**2)-ri-rj)
    c2=c1+d
    if c2<cost[j]:
      cost[j]=c2
      heappush(q,(c2,j))

print(cost[1])
P = int(input())
Q = int(input())
R = int(input())

Ans1 = P + Q
Ans2 = Q + R
Ans3 = R + P

if(Ans1 > Ans2):
	Ans1 = Ans2

if(Ans1 > Ans3):
	Ans1 = Ans3

print Ans1

### FIXED CODE ###

P,Q,R = map(int,input().split())

Ans1 = P + Q
Ans2 = Q + R
Ans3 = R + P

if(Ans1 > Ans2):
	Ans1 = Ans2

if(Ans1 > Ans3):
	Ans1 = Ans3

print (Ans1)
import itertools
N = int(input())
A = list(map(int, input().split()))
count = {}
for a in A:
  if a not in count:
    count[a] = 0
  count[a] += 1

  

def check(a):
  if count[a] > 1:
    return 0

  if 1 in count:
    if a == 1 and count[1] == 1:
      ans += 1
    return 0

  #print(a)
  ok = True
  sq_a = 1 + int(a**0.5)
  for s in itertools.chain([2], range(3, 1+int(a**0.5), 2)):
    c = s
    if a % c:
      continue
    while c < sq_a:
      if a % c == 0 and (c in count or (a//c) in count):
        #print(a, c)
        ok = False
        break
      c *= 2
  return ok
  
ans = 0
for a in A:
  ans += check(a)
print(ans)
    
    



### FIXED CODE ###

import itertools
N = int(input())
A = list(map(int, input().split()))
count = {}
for a in A:
  if a not in count:
    count[a] = 0
  count[a] += 1

def check(a):
  if count[a] > 1:
    return 0

  if 1 in count:
    if a == 1 and count[1] == 1:
      return 1
    return 0

  #print(a)
  ok = True
  sqr_a = 1 + int(a**0.5)
  for s in itertools.chain([2], range(3, sqr_a, 2)):
    if a % s:
      continue
    c = s
    while c < sqr_a:
      if a % c == 0 and (c in count or (a//c) in count):
        #print(a, c)
        ok = False
        break
      c *= 2
  return ok
  
ans = 0
for a in A:
  ans += check(a)
print(ans)
import queue
N,M = map(int,input().split())
tree = [[] for _ in range(M+1)]
for i in range(M):
    a,b = map(int,input().split())
    tree[a].append([b,a])
    tree[b].append([a,b])

que = queue.Queue()
que.put(1)
result = [[-1,100000] for _ in range(N+1)]
result[1][1] = 0

while(True):
    if que.empty():
        break
    nex = que.get()
    
    for i in tree[nex]:
        if result[i[0]][0] == -1  :
            result[i[0]][0] = nex
            result[i[0]][1] = result[nex][1] +1

            
            que.put(i[0])

for i in range(2,N+1):
    for j in tree[i]:
        if result[j[0]][1] == result[i][1] -1:
            result[i][0] = j[0] 
result = result[2:]
if result.count(-1) !=0:
    print("No")
else :
    print("Yes")
    for i in result:
        print(i[0])




### FIXED CODE ###

import queue
N,M = map(int,input().split())
tree = [[] for _ in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

que = queue.Queue()
que.put(1)
result = [-1]*(N+1)
result[1] = 0
while(True):
    if que.empty():
        break
    start = que.get()
    for i in tree[start]:
        if result[i] == -1:
            result[i] = start
            que.put(i)

if -1 in result[2:]:
    print("No")
else:
    print("Yes")
    for i in result[2:]:
        print(i)
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
a = 0
sum = 0
for i in range(N):
    A = list(map(int, input().split()))
    for j in range(M):
        sum += A[i][j] * B[j]
    if sum + C > 0:
        a += 1
        sum = 0
    else :
        sum = 0
print(a)

### FIXED CODE ###

N, M, C = map(int, input().split())
B = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(N)]
a = 0
sum = 0
for i in range(N):
    for j in range(M):
        sum += A[i][j] * B[j]
    if sum + C > 0:
        a += 1
        sum = 0
    else :
        sum = 0
print(a)
a, b, c, k = map(int, input().split())
 
if (a >= k):
    print(k)
elif ((a + b) >= k):
    print(a)
else:
    max_num = a - c
    print(max_num

### FIXED CODE ###

x = input()
y = input()
 
if x == y[:-1]:
	print('Yes')
else:
	print('No')
import collections 
import sys
sys.setrecursionlimit(3000)

n = int(input())
ab = [tuple(map(int,input().split())) for _ in range(n-1)]
tree = [[] for _ in range(n)]
for i in range(n-1):
  tree[ab[i][0]-1].append(ab[i][1]-1)
  tree[ab[i][1]-1].append(ab[i][0]-1)

ans = 0
ab_dic = collections.OrderedDict()
for i in ab:
  ab_dic[i] = 0

def dfs(i,before = -1,color = -1):
  k = 0
  for j in tree[i]:
    if j == before:
      continue
    if k == color:
      k += 1
    dfs(j,i,k)
    ab_dic[(i+1,j+1)] = k
    global ans
    ans = max(ans,k)
    k += 1

dfs(0)
print(ans+1)
for i in ab_dic:
  print(ab_dic[i]+1)



### FIXED CODE ###

import collections 
import sys
sys.setrecursionlimit(1000000)

n = int(input())
ab = [tuple(map(int,input().split())) for _ in range(n-1)]
tree = [[] for _ in range(n)]
for i in range(n-1):
  tree[ab[i][0]-1].append(ab[i][1]-1)
  tree[ab[i][1]-1].append(ab[i][0]-1)

ans = 0
ab_dic = collections.OrderedDict()
for i in ab:
  ab_dic[i] = 0

def dfs(i,before = -1,color = -1):
  k = 0
  for j in tree[i]:
    if j == before:
      continue
    if k == color:
      k += 1
    dfs(j,i,k)
    ab_dic[(i+1,j+1)] = k
    global ans
    ans = max(ans,k)
    k += 1

dfs(0)
print(ans+1)
for i in ab_dic:
  print(ab_dic[i]+1)
import collections
from functools import lru_cache

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

d = collections.Counter(a)
s = sum(a)
n1, n2, n3 = d[1], d[2], d[3]

@lru_cache(maxsize=None)
def calc(i1, i2, i3):
  if i1 == i2 == i3 == 0:
    return 0

  ex = n/(i1+i2+i3)
  if i1 > 0:
    ex += calc(i1-1, i2, i3) * (i1/(i1+i2+i3))
  if i2 > 0:
    ex += calc(i1+1, i2-1, i3) * (i2/(i1+i2+i3))
  if i3 > 0:
    ex += calc(i1, i2+1, i3-1) * (i3/(i1+i2+i3))

  return ex

print(calc(n1, n2, n3))

### FIXED CODE ###

import collections

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

d = collections.Counter(a)
s = sum(a)
n1, n2, n3 = d[1], d[2], d[3]

dp = [[0]*(n2+n3+1) for _ in range(n3+1)]
dp[n3][n2] = 1.0
ans = 0

for i in range(s, 0, -1):
  dp2 = [[0]*(n2+n3+1) for _ in range(n3+1)]
  for i3 in range(n3, -1, -1):
    for i2 in range(min(n2+n3, (i-i3*3)//2), -1, -1):
      i1 = i-i3*3-i2*2
      i0 = n-i1-i2-i3
      if i2 < 0 or i1 < 0 or i0 < 0: continue
      e0 = n/(i1+i2+i3)
      dp2[i3][i2] += dp[i3][i2] * i1/(i1+i2+i3)
      ans += dp[i3][i2] * e0*(i1/(i1+i2+i3))
      if i2 > 0:
        dp2[i3][i2-1] += dp[i3][i2] * i2/(i1+i2+i3)
        ans += dp[i3][i2] * e0*(i2/(i1+i2+i3))
      if i3 > 0 and i2 < n2+n3:
        dp2[i3-1][i2+1] += dp[i3][i2] * i3/(i1+i2+i3)
        ans += dp[i3][i2] * e0*(i3/(i1+i2+i3))
  dp = dp2

print(ans)
re,x=map(int,input().split())
print(' '.join(map(str,(list(range(x-re+1,x+re)))))

### FIXED CODE ###

re,x=map(int,input().split())
print(*list(range(x-re+1,x+re)))
import numpy as np
n,q=list(map(int, input().split()))
result = {i+1:0 for i in range(n)}
ar = np.eye(n)

for i in range(n-1):
    a,b = list(map(int, input().split()))
    ar[0:a,a-1:b] += 1
for i in range(q):
    a,b = list(map(int, input().split()))
    m = ar[a-1]
    for j in range(len(m)):
        if m[j] != 0:
            result[j+1] += b
r = list(result.values())
res = map(str, r)
print(' '.join(res))

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

n,q = map(int, input().split())
#長さn個のリストを入れ子にしたリストの作成：adj
adj = [[] for i in range(n)]

#adjに繋がっている要素を上流下流関わらず全て加える。
for j in range(n-1):
    a,b=map(int, input().split())
    adj[a-1].append(b-1)
    adj[b-1].append(a-1) 

#加算する値を合計したリストの作成
queries = [0 for i in range(n)]
for j in range(q):
    p, x = map(int, input().split())
    queries[p-1] += x

ans = [0 for i in range(n)]

#aの値，直前の値，直前のaの値
st = [(0, 0, -1)] 

#つながってる奴の一番後ろから処理していく。
#０スタート→1,2繋がってるなら2にいく。2に3が繋がってるなら次は3。
#3に繋がってるのがなければ1に戻る。
#この際，aの直前の値をタプルで保持したままリストに挿入して保管しておく。
while st:
    #stの先頭を取り出す。初期値は末尾のため-1
    l = st.pop()  
    ans[l[0]] = l[1] + queries[l[0]]
    for v in adj[l[0]]:
        if v != l[2]:
            st.append((v, ans[l[0]], l[0]))

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

A.sort()
S = sum(A)

if A[0] >= 0:
    print(S - A[0] * 2)
    tmp = A[0]
    for i in range(1, N - 1):
        print(tmp, A[i])
        tmp -= A[i]
    print(A[-1], tmp)

elif A[-1] <= 0:
    print(-S + A[-1] * 2)
    tmp = A[-1]
    for i in range(1, N):
        print(tmp, A[~i])
        tmp -= A[~i]

else:
    op = []
    tmp1 = A[-1]
    i = 1
    while A[i] < 0:
        op.append((tmp, A[i]))
        tmp1 -= A[i]
        i += 1
    tmp2 = A[0]
    i = ~1
    while A[i] >= 0:
        op.append((tmp2, A[~i]))
        tmp2 -= A[~i]
        i -= 1
    print(tmp1 - tmp2)
    for x, y in op:
        print(x, y)
        print(tmp1, tmp2)

### FIXED CODE ###

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

S = sum(map(abs,A))

if all([a>0 for a in A]):
    print(S-2*min(A))
    A = sorted(A)
    B = [A[0]]
    for i in range(1,N):
        B.append(B[-1]-A[i])
    for i in range(N-2):
        print(B[i],A[i+1])
    print(A[N-1],B[N-2])

elif all([a<0 for a in A]):
    print(S+2*max(A))
    A = sorted(A)
    B = [A[-1]]
    for i in range(N-1):
        B.append(B[-1]-A[i])
    for i in range(N-1):
        print(B[i],A[i])

else:
    print(S)
    A = sorted(A)
    B = [A[0]]
    for i in range(N):
        if N-1-2-i<0 or A[-2-i]<0:
            print(A[-1-i],B[-1])
            B.append(A[-1-i]-B[-1])
            break
        print(B[-1],A[-1-i])
        B.append(B[-1]-A[-1-i])
    C = [B[-1]]
    for i in range(1,N):
        if A[i]>=0:
            break
        print(C[-1],A[i])
        C.append(C[-1]-A[i])
N, M = map(int,input().split())
all_city = [list(map(int,input().split())) for i in range(M)]

city = {}
for i in all_city:
    if i[0] in city:
        city[i[0]].append(i[1])
    else:
        city[i[0]] = [i[1]]



for i,k in city.items():
    city[i] = sorted(k)

def change_Prefecture_code(prefecture):
    return str(prefecture).zfill(6)

def change_birth_code(birth_num):
    return str(birth_num).zfill(6)

for i in all_city:
    print(change_Prefecture_code(i[0]) + change_birth_code(city[i[0]].index(i[1]) + 1))

### FIXED CODE ###

X, Y = map(int, input().split())
print(int(X + Y / 2))
a, b, c, k = map(int, input().split())
if k <= a:
    k_pa, k_pb, k,pc = k , 0, 0 
elif k >= a and k-a <= b:
    k_pa, k_pb, k_pc = a, k-a, 0
elif k >= a and k-a >= b:
    k_pa, k_pb, k_pc = a, k-a, k-a-b
point = k_pa - (k-a-b)
print(point)

### FIXED CODE ###

a, b, c, k = map(int, input().split())
if k <= a:
    k_pa, k_pb, k_pc = k , 0, 0 
elif k > a and k-a <= b:
    k_pa, k_pb, k_pc = a, b, 0
elif k > a and k-a > b:
    k_pa, k_pb, k_pc = a, b, k-a-b
point = k_pa - (k-k_pa-k_pb)
print(point)
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
print(sum(a[:k]))


### FIXED CODE ###

value = input()
if value.isupper():
  print("A")
else:
  print("a")
n = map(int,raw_input().split())
n.sort()
for i in n
    print i,

### FIXED CODE ###

n = map(int,raw_input().split())
n.sort()
for i in n:
     print i,
#!/usr/bin/env python
# -*- conding: utf-8 -*-
import numpy as np

N, M = map(int, input().split())
A = []
B = []
for i in range(N):
    A_i, B_i = map(int, input().split())
    A.append(A_i)
    B.append(B_i)

min_value_index_list = np.argsort(A)

cnt = 0
result = 0
for i in range(N):
    cnt += B[min_value_index_list[i]]
    print(cnt)
    if M - cnt >= 0:
        result += A[min_value_index_list[i]] * B[min_value_index_list[i]]
        goal = M - cnt
    else:
        result += A[min_value_index_list[i]] * goal
        break
print(result)


### FIXED CODE ###

N,M = map(int,input().split())
li = [list(map(int,input().split())) for i in range(N)]
li=sorted(li,key=lambda x: x[0])
m_sum=0
for i in li:
	buy=min(M,i[1])
	m_sum+=i[0]*buy
	M-=buy
print(m_sum)