Harryxun/stf_run huggingface dataset:
import math
A, B, C, D = map(int, input().split())


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


Csita = A // C
Cue = B // C

Dsita = A // D
Due = B // D

CDsita = A // lcm(C, D)
CDue = B // lcm(C, D)


# Cで割れる時
tasu = 0
if (A % C == 0):
    tasu += 1
tasu += Cue - Csita

# Dで割れる時
if (A % D == 0):
    tasu += 1
tasu += Due - Dsita

# CでもDでも割れる
hiku = 0
if (A % (lcm(C, D)) == 0):
    hiku += 1
hiku += CDue - CDsita

print(B - A + 1 - (tasu - hiku))


### FIXED CODE ###

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


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(x, y):
    return (x * y) // gcd(x, y)


C_num = B // C - A // C

D_num = B // D - A // D

lcm = lcm(C, D)
CD_num = B // lcm - A // lcm


# Cで割れる時
tasu = 0
if (A % C == 0):
    tasu += 1
tasu += C_num

# Dで割れる時
if (A % D == 0):
    tasu += 1
tasu += D_num

# CでもDでも割れる
hiku = 0
if (A % lcm == 0):
    hiku += 1
hiku += CD_num

print((B - A + 1) - (tasu - hiku))
import math
n = int(input())
l = [input() for _ in range(5)]
print(math.ceil(n/min(l)+4))

### FIXED CODE ###

import math
n = int(input())
l = [int(input()) for _ in range(5)]
print(math.ceil(n/min(l))+4)
s = input()

ans += [int(i) for i in s]
print(ans)

### FIXED CODE ###

s = input()

ans = 0

for i in s:
  ans += int(i)

print(ans)
from sys import stdin
X = int(stdin.readline().rstrip())
exps=[]
for i in range(1,X+1):
    for j in range(2,X+1):
        if 1 <= i**j <= X:
            exps.append(i**j)
print(max(exps))


### FIXED CODE ###

from sys import stdin
X = int(stdin.readline().rstrip())
exps=[1]
for i in range(1,X+1):
    for j in range(2,X+1):
        if 1 <= i**j <= X:
            exps.append(i**j)
        else:
            break
print(max(exps))
w=input()

dict={}
alh="abcdefghijklmnopqrstuvwxyz"
for i in alh:
  dict[i]=0
for i in w:
  dict[i]+=1
flag=True
for j in range(len(dict)):
  if dict[j]%2==1:
    flag=False
if flag:
  print("Yes")
else:
  print("No")
  


### FIXED CODE ###

w=input()

dict={}
alh="abcdefghijklmnopqrstuvwxyz"
for i in alh:
  dict[i]=0
for i in w:
  dict[i]+=1
flag=True
for i in alh:
  if dict[i]%2==1:
    flag=False
if flag:
  print("Yes")
else:
  print("No")
import math
from functools import reduce

n,x = map(int,input().split())
lst=list(map(int,input().split()))
new_lst=[abs(i-x) for i in lst]

def gcd(*numbers):
  return reduce(math.gcd, numbers)
def gcd_list(numbers):
  return reduce(math.gcd, numbers)

print(gcd(*new_lst))


### FIXED CODE ###

import fractions
from functools import reduce

n,x = map(int,input().split())
lst=list(map(int,input().split()))
new_lst=[abs(i-x) for i in lst]

def gcd(*numbers):
  return reduce(fractions.gcd, numbers)
def gcd_list(numbers):
  return reduce(math.gcd, numbers)

print(gcd(*new_lst))
a,b = map(int,input().split())
x = (a+b)/2
if (a+b)%2 = 0:
  print(int(x))
else:
  print(int(x)+1)


### FIXED CODE ###

a,b = map(int,input().split())
x = (a+b)/2
if (a+b)%2 == 0:
  print(int(x))
else:
  print(int(x)+1)
a,b=map(float,input().split())


print(int(a*(b*100)/100)

### FIXED CODE ###

x=input().split()
a=int(x[0])
b=round(float(x[1])*100)
print(int(a*b//100))
N = int(input())
A = list(map(int, input().split()))
M = N//2
if N % 2 == 1 and A.count(0) == 1 and all(A.count(i*2+2)==2 for i in range(M)):
    print((2 ** M) % (10**9+7))
elif N % 2 == 0 and all(A.count(i*2+1)==2 for i in range(M)):
    print((2 ** M) % (10**9+7))
else:
    print(0)

### FIXED CODE ###

A, op, B = input().split()
if op == '+':
    print(int(A) + int(B))
if op == '-':
    print(int(A) - int(B))
A, B, C = [int(i) for i in input().split()]
print(max(B // A, C)

### FIXED CODE ###

A, B, C = [int(i) for i in input().split()]
print(min(B // A, C))
import sys
n,m = map(int,input().split())
ans = [-1 for i in range(n)]
check = [0 for i in range(n)]
if n == 1:
    s,c = map(int,input().split())
    print(c)
    sys.exit()
else:
    for i in range(m):
        s,c = map(int,input().split())
        if ans[s-1] == -1:
            ans[s-1] = c
        else:
            if c == ans[s-1]:
                continue
            else:
                print(-1)
                sys.exit()
        if s-1 == 0:
            if c == 0:
                print(-1)
                sys.exit()
    for i in range(1,n):
        if ans[i] == -1:
            ans[i] = 0
    if ans[0] == -1:
        ans[0] = 1
    ans2 = ''
    for i in range(n):
        ans2 += str(ans[i])
    print(ans2)

### FIXED CODE ###

import sys
n,m = map(int,input().split())
ans = [-1 for i in range(n)]
if n == 1:
    if m == 0:
        print(0)
        sys.exit()
    else:
        for i in range(m):
            s,c = map(int,input().split())
            if ans[s-1] == -1:
                ans[s-1] = c
            else:
                if c == ans[s-1]:
                    continue
                else:
                    print(-1)
                    sys.exit()
        print(ans[0])
else:
    for i in range(m):
        s,c = map(int,input().split())
        if s-1 == 0:
            if c == 0:
                print(-1)
                sys.exit()
            else:
                if ans[s-1] == -1:
                    ans[s-1] = c
                else:
                    if c == ans[s-1]:
                        continue
                    else:
                        print(-1)
                        sys.exit()
        else:
            if ans[s-1] == -1:
                    ans[s-1] = c
            else:
                if c == ans[s-1]:
                        continue
                else:
                    print(-1)
                    sys.exit()
    if ans[0] == -1:
        ans[0] = 1
    for i in range(n):
        if ans[i] == -1:
            ans[i] = 0
    ans2 = ""
    for i in range(n):
        ans2 += str(ans[i])
    print(ans2)
n = int(input())
x = sorted(list(map(int, input().split())), reverse = True)
x_2 = list(map(lambda x:x ** 2, x))
ichi = sum(x)
jijou = sum(x_2)
re = 10 ** 100


#def ji(p, x):
#    ans = p * (p - 2 * x)
#    return ans

for p in range(x[n], x[0] + 1):
    second = n * (p ** 2)
    third = -2 * p * ichi
    summ = jijou + second + third

    if re > summ:
        re = summ

print(re)

#for i in range(x[i]):


### FIXED CODE ###

n = int(input())
x = sorted(list(map(int, input().split())), reverse = True)
x_2 = list(map(lambda x:x ** 2, x))
ichi = sum(x)
jijou = sum(x_2)
re = 10 ** 100


#def ji(p, x):
#    ans = p * (p - 2 * x)
#    return ans

for p in range(x[-1], x[0] + 1):
    second = n * (p ** 2)
    third = -2 * p * ichi
    summ = jijou + second + third

    if re > summ:
        re = summ

print(re)

#for i in range(x[i]):
# input
S = input()

fl = True
for i, s in range(0, 4):
    if S[i] == S[i + 1]:
        print("Bad")
        fl = False
        break

if fl is True:
    print("Good")

### FIXED CODE ###

# input
S = input()

fl = True
for i in range(0, 3):
    if S[i] == S[i + 1]:
        print("Bad")
        fl = False
        break

if fl is True:
    print("Good")
n,m=map(int, input().split())
r = []

for i in range(m):
    r.append(str(0))

for i in range(m):
    s,c = map(int, input().split())
    r[s-1] = str(c)

if r[0] == '0':
    print('-1')
else:
    print(''.join(r))



### FIXED CODE ###

n,m=map(int, input().split())
r = []

for i in range(n):
    r.append(str(0))

if n == 1 and m == 0:
    print('0')
    exit()
if n == 2 and m == 0:
    print('10')
    exit()
if n == 3 and m == 0:
    print('100')
    exit()

for i in range(m):
    s,c = map(int, input().split())
    if n == 1 and s == 1 and c == 0:
        print('0')
        exit()
    elif n > 1 and s == 1 and c == 0:
        print('-1')
        exit()

    if int(r[s-1]) == 0:
        r[s-1] = str(c)
    elif int(r[s-1]) == c:
        r[s-1] = str(c)
    else:
        print('-1')
        exit()

if n > 1 and r[0] == '0':
    r[0] = '1'
    print(''.join(r))
else:
    print(''.join(r))
n,k = map(int,input().split())
a = list(map(int,input().split()))
l = [1,a[0]]
tp = a[0]-1
while True:  
  if a[tp] not in l: 
    l.append(a[tp])
    tp = a[tp] -1
  else:
    l.append(a[tp])
    break
    
last = l[-1]

loop = len(l[l.index(last):-1])
first = l.index(last)
if len(l)>k:
  print(l[k])
  exit()
k -=first
k %=loop
if k==0:
  k+=loop
print(l[k+first])

### FIXED CODE ###

s = input()
t = input()

if t[:-1]==s:
  print("Yes")
else:
  print("No")
import numpy as np
import itertools
 
N, M, X = list(map(int, input().split()))
Arr = np.zeros((N,M+1))
List = np.zeros(M)
 
for i in range(N):
    Arr[i] = list(map(int, input().split()))
    
for j in range(M):
    List[j] = np.sum(Arr[:,j])

if np.any(List<10):
    print(-1)

else:
    List = sorted(List)
    for i in range(N+1):
        for team in itertools.combinations(List,i):
            Sum = np.sum(Arr[team,:])
            if np.all(Sum>=10):
                break

### FIXED CODE ###

N,M,X = map(int,input().split())
B = [list(map(int,input().split())) for i in range(N)]
ANS = 10**5 * 12 + 1
for i in range(1<<N):
    SCORE=[0]*M
    MONEY=0
    for j in range(N):
        if (1<<j) & i != 0:
            MONEY+=B[j][0]
            for k in range(M):
                SCORE[k]+=B[j][k+1]
    if min(SCORE)>=X:
        ANS=min(ANS,MONEY)
if ANS == 10**5 * 12 + 1:
    print(-1)
else:
    print(ANS)
import collections

n = int(input())
v = [int(i) for i in input().split()]

v1 = [v[i] for i in range(0,n,2)]
v2 = [v[i] for i in range(1,n,2)]

count1 = collections.Counter(v1)
count2 = collections.Counter(v2)

if v1 == v2:
    print(len(v1))

elif len(count1) == 1 and len(count2) == 1:
    print(0)

else:
    res = 0
    ct1 = list(count1.values())
    ct2 = list(count2.values())

    for i in ct1[1:]:
        res = res + ct1[i]

    for i in ct2[1:]:
        res = res + ct2[i]
    print(res)




### FIXED CODE ###

import collections
 
n = int(input())
v = [int(i) for i in input().split()]
 
v1 = [v[i] for i in range(0,n,2)]
v2 = [v[i] for i in range(1,n,2)]
 
count1 = collections.Counter(v1).most_common(2)
count2 = collections.Counter(v2).most_common(2)

if count1[0][0] != count2[0][0]:
    res = len(v1) - count1[0][1] + len(v2) - count2[0][1]
    print(res)
else:
    if len(count1) == 1:
        print(len(v1))
    else:
        res1 = len(v1) - count1[0][1] + len(v2) - count2[1][1]
        res2 = len(v1) - count1[1][1] + len(v2) - count2[0][1]
        print(min(res1,res2))
import sys
import threading

sys.setrecursionlimit(200000000)
threading.stack_size(134217728)


class SearchProblem(object):
    def __init__(self, N, H):
        self.N = N
        self.H = H

    def isEnd(self, i):
        return i == self.N

    def succ(self, i):
        res = []
        if i + 1 <= self.N:
            res.append((i + 1, abs(self.H[i + 1] - self.H[i])))
        if i + 2 <= self.N:
            res.append((i + 2, abs(self.H[i + 2] - self.H[i])))
        return res


def solve(problem: SearchProblem):
    memo = {}

    def future_cost(s):
        if s in memo:
            return memo[s]

        if problem.isEnd(s):
            memo[s] = 0
            return 0
        else:
            memo[s] = min(
                cost + future_cost(next_state) for next_state, cost in problem.succ(s)
            )
            return memo[s]

    return future_cost(1)


def main():
    N = int(input())
    H = [None] + [int(x) for x in input().split(" ")]
    problem = SearchProblem(N, H)
    print(solve(problem))


if __name__ == "__main__":
    main_thread = threading.Thread(target=main)
    main_thread.start()
    main_thread.join()


### FIXED CODE ###

def solve(n):
    table = [0 for i in range(N + 1)]
    for i in range(1, n + 1):
        if i == 1:
            table[1] = 0
        elif i == 2:
            table[2] = abs(H[2] - H[1])
        else:
            table[i] = min(
                table[i - 1] + abs(H[i] - H[i - 1]), table[i - 2] + abs(H[i] - H[i - 2])
            )
    return table[n]


if __name__ == "__main__":
    N = int(input())
    H = [0] + [int(x) for x in input().split(" ")]

    print(solve(N))
import sys

input = sys.stdin.readline

def main():
    def hash_ij(i, j):
        if i + j == 0: return 0
        res = hash_table[i][j]
        if res == -1:
            if i > 0:
                res = (hash_ij(i - 1, j - 1) * base + target[j - 1]
                       - target[i - 1] * power(j - i)) % hash_md
            else:
                res = (hash_ij(i, j - 1) * base + target[j - 1]) % hash_md
            hash_table[i][j] = res
        return res

    def power(e):
        if e == 0: return 1
        res = pw[e]
        if res == -1:
            res = pw[e] = power(e - 1) * base % hash_md
        return res

    n = int(input())
    target = input()[:-1]

    # 初期化
    base = 29  # 文字種以上の素数
    hash_md = pow(3, 37)  # 2のべき乗以外がよい
    ord_a = ord('a')
    target = [ord(c) - ord_a for c in target]
    hash_table = [[-1] * (len(target) + 1) for _ in range(len(target))]
    pw = [-1] * (len(target) + 1)

    ok = 0
    ng = n // 2 + 1
    while ok + 1 < ng:
        br = False
        w = (ok + ng) // 2
        for i in range(n - 2 * w + 1):
            ptn = hash_ij(i, i + w)
            for j in range(i + w, n - w + 1):
                if hash_ij(j, j + w) == ptn:
                    ok = w
                    br = True
                    break
            if br: break
        else:
            ng = w
    print(ok)

main()


### FIXED CODE ###

# YouTube
def main():
    n = int(input())
    s = input()
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i, c in enumerate(s):
        for j in range(n):
            if c == s[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
    ans = 0
    for i in range(n):
        for j in range(i+1,n+1):
            tmp=min(dp[i][j],j-i)
            ans=max(tmp,ans)
    print(ans)

main()
a,b = map(int, raw_input().split());

print"2*(a+b) "+"a*b";

### FIXED CODE ###

a, b = map(int, raw_input().split())

print a*b, 2*(a+b)
N,M=map(int,input().split())
X=list(map(int,input().split()))

if N >= M:
  print(0)
else:
  X.sort()
  diff=[[0,0]]*(M-1)
  for i in range(M-1):
    diff[i]=[X[i+1]-X[i],i]
  diff.sort(key=lambda x:x[0])
  if N == 1:
    print(X[-1]-X[0])
    
  else:
    while N>0:
      if diff[-1][1]==0 or diff[-1][1]==M-2:
        N-=1
        diff.pop()
      elif N > 1:
        N-=2
        diff.pop()
      else:
        N-=1
  ans=0
  for x in diff:
    ans+=x[0]
print(ans)
        

### FIXED CODE ###

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

if N >= M:
    print(0)
else:
    X.sort()
    spot = [0]*M
    diff = [[0, 0]]*(M-1)
    for i in range(M-1):
        diff[i] = [X[i+1]-X[i], i]
    diff.sort(key=lambda x: x[0])
    if N == 1:
        print(X[-1]-X[0])

    else:
        ans = X[-1] - X[0]
        for i in range(N-1):
            tmp = diff.pop()
            ans -= tmp[0]
        print(ans)
print((input())^3)

### FIXED CODE ###

print(int(input())**3)
def make_divisors(n,m):
    divisors = []
    for i in range(1, (n//m)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
n,m=map(int,input().split())
print(max(make_divisors(n,m)))

### FIXED CODE ###

def make_divisors(n,m):
    divisors = []
    for i in range(1,min(int(m**(1/2))+1,int(m//n)+1)):
      if m % i == 0:
          divisors.append(i)
          if i != m // i and m//i<=m//n:
              divisors.append(m//i)
    return divisors
n,m=map(int,input().split())
print(max(make_divisors(n,m)))
N = int(input())
kekka = 0
for i in range(1:N+1):
    if len(str(i)) % 2 == 1:
        kekka += 1


### FIXED CODE ###

N = int(input())
kekka = 0
for i in range(1,N+1):
    if len(str(i)) % 2 == 1:
        kekka += 1

print(kekka)
import sys
input = sys.stdin.readline

MOD=10**9+7
 
n=int(input())
edge=[[] for _ in range(n)]
for _ in range(n-1):
  p,q = [int(i)-1 for i in input().split()]
  edge[p].append(q)
  edge[q].append(p)

flag=[0]*n

if n==1:
  ans=2
else:
  dp=[[0] * 2 for i in range(n)]
  for i in range(n):
    if len(edge[i])==1:
      dp[i]=[1,1]
      flag[i]=1
    else:
      dp[i]=[0,0]
  dp[0]=[0,0]
  stack = [0]
  while len(stack)!=0:
    term=0
    white=1
    black=1
    for i in range(len(edge[stack[len(stack)-1]])):
      if flag[edge[stack[len(stack)-1]]]==0:
        flag[edge[stack[len(stack)-1]][i]]=1
        stack.append(edge[stack[len(stack)-1]][i])
        term=1
      else:
        sub1=max(1,(dp[edge[stack[len(stack)-1]][i]][0]+dp[edge[stack[len(stack)-1]][i]][0])%MOD)
        sub2=max(1,dp[edge[stack[len(stack)-1]][i]][0])
        white=(white*sub1)%MOD
        black=(black*sub2)%MOD
    if term == 0:
      dp[stack[len(stack)-1]]=[white,black]
      stack.pop()
  
  ans = (dp[0][0]+dp[0][1])%MOD


print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

MOD=10**9+7
 
n=int(input())
edge=[[] for _ in range(n)]
for _ in range(n-1):
  p,q = [int(i)-1 for i in input().split()]
  edge[p].append(q)
  edge[q].append(p)

flag=[0]*n
flag[0]=1
if n==1:
  ans=2
else:
  dp=[[0] * 2 for i in range(n)]
  for i in range(n):
    if len(edge[i])==1:
      dp[i]=[1,1]
      flag[i]=1
    else:
      dp[i]=[0,0]
  dp[0]=[0,0]
  stack = [0]
  while len(stack)!=0:
    term=0
    white=1
    black=1
    length=len(stack)-1
    for i in range(len(edge[stack[length]])):
      if flag[edge[stack[length]][i]]==0:
        flag[edge[stack[length]][i]]=1
        stack.append(edge[stack[length]][i])
        term=1
      else:
        sub1=max(1,(dp[edge[stack[length]][i]][0]+dp[edge[stack[length]][i]][1])%MOD)
        sub2=max(1,dp[edge[stack[length]][i]][0])
        white=(white*sub1)%MOD
        black=(black*sub2)%MOD
    if term == 0:
      dp[stack[length]]=[white,black]
      stack.pop()
  
  ans = (dp[0][0]+dp[0][1])%MOD

print(ans)
N ,K = int(input().strip().split())
a = list(map(int, input().strip().split()))
for i range (N):
  if a[i] >= K:
    p += 1
print(p)

### FIXED CODE ###

N,K = input().strip().split()
N = int(N)
K = int(K)
a = list(map(int, input().split()))
p = 0
for i in range(N):
  if a[i] >= K:
    p += 1
print(p)
N=int(input())
ans=0
mul=1
while ans<=N:
    ans=6*(mul**2)
    mul+=1
ANS={}
for i in range(1,101):
    for j in range(i,101):
        for k in range(j,101):
            if i!=j and j!=k and k!=i:
                ANS[i*i+j*j+k*k+i*j+j*k+i*k]=6
            elif i==j and j==k and k==i:
                ANS[i*i+j*j+k*k+i*j+j*k+i*k]=1
            else:
                ANS[i*i+j*j+k*k+i*j+j*k+i*k]=3
for Z in range(1,N+1):
    if Z in ANS.keys():
        print(ANS[Z])
    else:
        print(0)

### FIXED CODE ###

L,R,d=map(int,input().split())
cnt=0
for i in range(L,R+1):
    if i%d==0:
        cnt+=1
print(cnt)
import sys

def makec(c):
  alph = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
           'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
  if c[-1] == 'z':
    return makec(c[-1])
  else:
    pos = alph.index(c[-1]) + 1
    c = c[:-1] + alph[pos]
    return c


def f(S, K, c):
  if K == 0:
    return c[:-1]
  
  if c in S:
    c = c + 'a'
    return f(S, K-1, c)
  else:
    c = makec(c)
    return f(S, K, c)

def main():
  input = sys.stdin.readline
  S = str(input().strip())
  K = int(input())
  ans = f(S, K, 'a')
  print(ans)


if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys


def main():
  input = sys.stdin.readline
  S = str(input().strip())
  K = int(input())
  max = min(5, len(S))
  sub = []
  for i in range(len(S)):
    for j in range(1, max+1):
      if i+j > len(S):
        continue
      sub.append(S[i:i+j])
  sub = sorted(list(set(sub)))
  print(sub[K-1])


if __name__ == '__main__':
  main()
n, m = map(int, input().split())

xy_dict = {}
for i in range(1,n+1):
    xy_dict[i] = []

for i in range(m):
    x,y = map(int, input().split())
    xy_dict[x].append(y)

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

def get_longest(x):
    global dp

    if( dp[x] > 0):
        return dp[x]
    else:
        y_list = xy_dict[x]
        temp_max = 0
        for y in y_list:
            temp_max = max(temp_max, get_longest(y)+1)

        dp[x] = temp_max
        return temp_max

for i in range(1,n+1):
    get_longest(i)

print(max(dp))

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

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

xy_dict = {}
for i in range(1,n+1):
    xy_dict[i] = []

for i in range(m):
    x,y = map(int, input().split())
    xy_dict[x].append(y)

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

def get_longest(x):
    global dp

    if( dp[x] >= 0):
        return dp[x]
    else:
        y_list = xy_dict[x]
        temp_max = 0
        for y in y_list:
            temp_max = max(temp_max, get_longest(y)+1)

        dp[x] = temp_max
        return temp_max

ans = 0
for i in range(1,n+1):
    ans = max(ans, get_longest(i))

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

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

for i in range(1,n+1):
    dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)
    if i in a : dp[i]=0
print(dp[n])

### FIXED CODE ###

n,m=map(int,input().split())
a=set([int(input()) for i in range(m)])
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:dp[i]=0
print(dp[n])
N, K = map(int, input().split())
l = soted(map(int, input().split()), reversed=True)
print(sum(l[:K]))

### FIXED CODE ###

N, K = map(int, input().split())
l = sorted(map(int, input().split()), reverse=True)
print(sum(l[:K]))
n, ww = map(int, input().split())
w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (110) for i in range(100100)]

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

print(dp[n - 1][ww])

### FIXED CODE ###

n, ww = map(int, input().split())
w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (100100) for i in range(110)]

for i in range(n):
    for j in range(ww + 1):
        if j - w[i] >= 0:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])

        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

print(dp[n][ww])
n,m=map(int,input().split())
a=[0]*n
b=[0]*n
for i in range(n):
    a[i],b[i]=map(int,input().split())
def merge(rr):
    mid=len(rr[0])
    c=int(mid/2)
    if mid>1:
        left=merge([rr[0][:c],rr[1][:c]])
        right=merge([rr[0][c:],rr[1][c:]])
        ar=[]
        br=[]
        while len(left[0])!=0 and len(right[0])!=0:
            if left[0][0]<right[0][0]:
                ar.append(left[0].pop(0))
                br.append(left[1].pop(0))
            else:
                ar.append(right[0].pop(0))
                br.append(right[1].pop(0))
        if len(left[0])!=0:
            ar.extend(left[0])
            br.extend(left[1])
        elif len(right[0])!=0:
            ar.extend(right[0])
            br.extend(right[1])
        rr=[ar,br]
    return rr
rr=[a,b]
re=merge(rr)
tot=0
sum=0
while(1):
    if tot+re[1][0]<=m:
        tot+=re[1][0]
        sum+=re[0][0]*re[1][0]
        re[1].pop(0)
        re[0].pop(0)
        if len(re[1])==0:
            break
    else:
        break
sum+=re[0][0]*(m-tot)
print(sum)


### FIXED CODE ###

import numpy as np

n,m = map(int,input().split())
a=[0] * n
b=[0] * n
for i in range(n):
    a[i],b[i] = map(int,input().split())

mk = np.array([a,b])
#print(m)
index = np.argsort(mk)
#print(index)
mn = np.array([mk[0,index[0,:]],mk[1,index[0,:]]])
#print(mn)

sum = 0
for i in range(n):
    if mn[1][i] <= m:
        sum += mn[0][i] * mn[1][i]
        m = m - mn[1][i]

    else:
        sum += mn[0][i] * m
        break
print(sum)