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

import sys
sys.setrecursionlimit(10**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 sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def main():
    N = II()
    a_list = []

    for i in range(N):
        a = II()
        a_list.append(a)


    g = []

    from bisect import bisect_left

    for i in range(N):
        a = a_list[i]
        if len(g) == 0:
            g.append(a)
        else:
            pos = bisect_left(g, a)
            dprint(g, a, pos)
            if pos >= 1:
                g[pos-1] = a
            else:
                g.insert(0, a)
    dprint(g)
    print(len(g))
main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**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 sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def main():
    N = II()
    a_list = []

    for i in range(N):
        a = II()
        a_list.append(a)


    from bisect import bisect_left
    from collections import deque
    g = deque()

    for i in range(N):
        a = a_list[i]
        if len(g) == 0:
            g.appendleft(a)
        else:
            pos = bisect_left(g, a)
            dprint(g, a, pos)
            if pos >= 1:
                g[pos-1] = a
            else:
                #g.insert(0, a)
                g.appendleft(a)
    dprint(g)
    print(len(g))
main()
### BUGGY CODE ###

import math
from functools import reduce

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

k = int(input())
sum_ = 0

for i in range(1, k+1):
    for j in range(1, k+1):
        for l in range(1, k+1):
            sum_ += gcd_list([i, j, l])
            
print(sum_)

### FIXED CODE ###

import math

k = int(input())
sum_ = 0

for i in range(1, k+1):
    for j in range(1, k+1):
        x = math.gcd(i, j)
        for l in range(1, k+1):
            sum_ += math.gcd(x, l)
            
print(sum_)
### BUGGY CODE ###

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

for i in range(H):
	a = list(map(int,input().split()))
	A[i] = a
for i in range(H):
	b = list(map(int,input().split()))
	B[i] = b

D = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
R = 160*80
dp = [[[False for k in range(R)] for j in range(W)] for i in range(H)]
dp[0][0][D[0][0]] = True
for i in range(H):
	for j in range(W):
		r = 80 * (i+j+2)
		for n in range(r):
			if not dp[i][j][n]:
				continue
			if j != W-1:
				d = D[i][j+1]
				dp[i][j+1][n+d] = True
				dp[i][j+1][abs(n-d)] = True
			if i != H-1:
				d = D[i+1][j]
				dp[i+1][j][n+d] = True
				dp[i+1][j][abs(n-d)] = True

h,w = H-1, W-1
for i in range(R):
	if dp[h][w][i]:
		print(i)
		exit()

### FIXED CODE ###

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

for i in range(H):
	a = list(map(int,input().split()))
	A[i] = a
for i in range(H):
	b = list(map(int,input().split()))
	B[i] = b

D = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
R = 160*80
"""
dp = [[[False for k in range(R)] for j in range(W)] for i in range(H)]
dp[0][0][D[0][0]] = True
for i in range(H):
	for j in range(W):
		r = 80 * (i+j+2)
		for n in range(r):
			if not dp[i][j][n]:
				continue
			if j != W-1:
				d = D[i][j+1]
				dp[i][j+1][n+d] = True
				dp[i][j+1][abs(n-d)] = True
			if i != H-1:
				d = D[i+1][j]
				dp[i+1][j][n+d] = True
				dp[i+1][j][abs(n-d)] = True

"""
dp = [[0 for j in range(W)] for i in range(H)]
dp[0][0] = 2**(R + D[0][0]) | 2**(R - D[0][0])
for i in range(H):
	for j in range(W):
		if j != W-1:
			d = D[i][j+1]
			dp[i][j+1] |= (dp[i][j] << d | dp[i][j] >> d)
		if i != H-1:
			d = D[i+1][j]
			dp[i+1][j] |= (dp[i][j] << d | dp[i][j] >> d)
h,w = H-1, W-1
for i in range(R):
	mask = 2 ** (R+i) | 2 ** (R-i)
	if dp[h][w] & mask > 0:
		print(i)
		exit()
### BUGGY CODE ###

import numpy as np
from collections import deque

N = int(input())
A = np.fromiter(list(map(int, input().split(' '))), dtype=np.int32)
A.sort()

results = deque()
while len(A) > 0:
    if not (len(A) > 1 and A[0] == A[1]):
        results.append(A[0])
    A = A[A % A[0] != 0]

print(len(results))


### FIXED CODE ###

from collections import Counter
import numpy as np

A_MAX = 10 ** 6 + 1

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

dp = np.zeros(shape=A_MAX, dtype=np.int64)

if A[1] == 1:
    print(1)
elif A[1] > 1:
    print(0)
else:
    for a in A.keys():
        multiples = np.arange(a, A_MAX, a)
        np.add.at(dp, multiples, 1)

    ans = 0
    for a, count in A.items():
        if count > 1:
            continue
        if dp[a] == 1:
            ans += 1

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

from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n,m=MI()
    aa=LI()
    aa.sort(reverse=True)
    fin=set()
    hp=[]
    heappush(hp,[-aa[0]*2,0,0])
    fin.add((0,0))
    ans=0
    for _ in range(m):
        a,i,j=heappop(hp)
        ans-=a
        if i+1<n and (i+1,j) not in fin:
            heappush(hp,[-aa[i+1]-aa[j],i+1,j])
            fin.add((i+1,j))
        if j+1<n and (i,j+1) not in fin:
            heappush(hp,[-aa[i]-aa[j+1],i,j+1])
            fin.add((i,j+1))

    print(ans)

main()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def ok(c):
        cnt = 0
        i = 0
        for a in aa[::-1]:
            while i < n and a + aa[i] >= c: i += 1
            cnt += i
            if cnt >= m: return True
        return False

    n, m = MI()
    aa = LI()
    aa.sort(reverse=True)
    # 握手の回数がm以上になるような、1回の握手の幸福度の最低値を求める
    l = aa[-1] * 2 - 1
    r = aa[0] * 2 + 1
    while l + 1 < r:
        c = (l + r) // 2
        if ok(c):
            l = c
        else:
            r = c
    min_once = l
    # 幸福度がmin_once以上になる握手の総和を求める
    ans = 0
    i = 0
    s = 0
    cnt = 0
    for a in aa[::-1]:
        while i < n and a + aa[i] >= min_once:
            s += aa[i]
            i += 1
        ans += s + i * a
        cnt += i
    # 握手の回数がmを越えたときはその分の幸福度を引く
    if cnt - m:
        ans -= min_once * (cnt - m)
    print(ans)

main()
### BUGGY CODE ###

n=int(input())
from collections import deque
s=deque(input())
R=[]
G=[]
B=[]
i=0
while s:
    x=s.popleft()
    if x=='R':
        R.append(i)
    elif x=='G':
        G.append(i)
    else:
        B.append(i)
    i+=1
#print(R)    
ans=0
for i in R:
    for j in G:
        for k in B:
            if not(i+j==2*k or j+k==2*i or k+i==2*j):
                ans+=1
print(ans)                

### FIXED CODE ###

from itertools import product
from collections import deque
n = int(input())
s = deque(input())
R = []
G = []
B = []
i = 0
while s:
    x = s.popleft()
    if x == 'R':
        R.append(i)
    elif x == 'G':
        G.append(i)
    else:
        B.append(i*2)
    i += 1
ans = len(R)*len(G)*len(B)
# print(len(R))
# print(len(G))
# print(len(B))
# print(R)
# print(G)
# print(B)
B = set(B)
S = product(R, G)
for i, j in S:
    if i + j in B:
        ans -= 1
    if 4 * i - 2*j in B:
        ans -= 1
    if 4 * j - 2 * i in B:
        ans -= 1
print(ans)
### BUGGY CODE ###

def main():
    from copy import deepcopy
    n, m = map(int, input().split())
    s = [i == "B" for i in input()]
    ab = [list(map(int, input().split())) for _ in [0]*m]
    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]

    g2 = [[0, 0] for _ in [0]*n]

    for i in range(n):
        for j in g[i]:
            g2[i][s[j]] += 1

    ss = []
    for i, (j, k) in enumerate(g2):
        if (j == 0 and k > 0) or (j > 0 and k == 0):
            ss.append(i)

    while ss:
        i = ss.pop()
        c = s[i]
        for j in deepcopy(g[i]):
            g[j].remove(i)
            g2[j][c] -= 1
            p, q = g2[j]
            if (p == 0 and q > 0) or (p > 0 and q == 0):
                ss.append(j)
        g[i] = set()

    for i in g:
        if len(i) > 0:
            print("Yes")
            return
    print("No")


main()


### FIXED CODE ###

def main():
    from sys import stdin
    input = stdin.readline
    n, m = map(int, input().split())
    s = [i == "B" for i in input()]
    ab = [list(map(int, input().split())) for _ in [0]*m]
    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]

    g2 = [[0, 0] for _ in [0]*n]

    for i in range(n):
        for j in g[i]:
            g2[i][s[j]] += 1

    ss = []
    for i, (j, k) in enumerate(g2):
        if (j == 0 and k > 0) or (j > 0 and k == 0):
            ss.append(i)

    while ss:
        i = ss.pop()
        c = s[i]
        for j in g[i]:
            if i != j:
                g[j].remove(i)
            g2[j][c] -= 1
            p, q = g2[j]
            if (p == 0 and q > 0) or (p > 0 and q == 0):
                ss.append(j)
        g[i] = set()

    for i in g:
        if len(i) > 0:
            print("Yes")
            return
    print("No")


main()
### BUGGY CODE ###

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

for j in range(1,N+1):
    print(A.count(j))

### FIXED CODE ###

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

D={}
for i in range(N-1):
    if (A[i] in D.keys())==True:
        D[A[i]]+=1
    elif (A[i] in D.keys())==False:
        D[A[i]]=1
for i in range(1,N+1):
    try:
        print(D[i])
    except:
        print(0)
### BUGGY CODE ###

N, K = map(int,input().split())
moves = []

mod = 998244353

for _ in range(K):
    L, R = map(int,input().split())
    # for d in range(L, R+1):
    #     moves.append(d)
    moves.append((L, R))
# moves.sort()

dp = [0] * (N + 1)
dp[1] = 1
# for dis in moves:
#     dp[dis] = 1
# print(moves)

for n in range(1, N+1):
    for L, R in moves:
        if n - L <= 0 :
            continue
        for dis in range(L, R+1):
            if n - dis >= 1:
                dp[n] += dp[n - dis]
            else:
                break

# print(dp)
print(dp[N] % mod)


### FIXED CODE ###

n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])
### BUGGY CODE ###


n = int(input())
data = []
data2 = []
ans = 0
for i in range(n):
    a = input()
    p = sorted(a)
    if p not in data:
        data.append(p)
        data2.append(1)
    else:
        data2[data.index(p)] += 1

#print(data2)
for i in data2:
    ans+=int(i*(i-1)/2)
print(ans)

### FIXED CODE ###

n = int(input())
data = []
for i in range(n):data.append(sorted(input()))
data, backup, ans, temp = sorted(data), [], 0, 1
for i in data:
    if backup==i:temp+=1
    else:ans, temp = ans + int(temp*(temp-1)/2), 1
    backup = i
ans+= int(temp*(temp-1)/2)
print(ans)
### BUGGY CODE ###

nk = input().split()
n , k = int(nk[0]), int(nk[1])
a = [int(i) for i in input().split()]

t = 1
tl = [1]
for i in range(len(a)):
    t  = a[t-1]
    
    if t in tl:
        break
    else:
        tl.append(t)
tl2 = tl[tl.index(t):len(tl)]
         
# print(tl)
# print(tl2)

ans = 0

if k <= len(tl):
    ans = tl[k]
else:
    k = k - len(tl)
    j = k % len(tl2)
    ans = tl2[j]

print(ans)

### FIXED CODE ###

nk = input().split()
n , k = int(nk[0]), int(nk[1])
a = [int(i) for i in input().split()]

t = 1
tl = [1]
ts = {1}


for i in range(len(a)):
    
    t = a[t-1]
    if t in ts:
        break
    else:
        tl.append(t)
        ts.add(t)

tl2 = tl[tl.index(t):len(tl)]
         
# print(tl)
# print(tl2)

ans = 0

if k < len(tl):
    ans = tl[k]
else:
    k = k - len(tl)
    j = k % len(tl2)
    ans = tl2[j]

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

H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]


max_magic = 0
for a, _ in magic:
    max_magic = max(max_magic, a)

amount = H + 1
dp = [float('inf')] * (amount + max_magic)
dp[0] = 0

ret = float('inf')

for amt in range(1, amount + max_magic):
    t = [dp[amt - a] + b if amt - a >= 0 else float('inf') for a, b in magic]
    dp[amt] = min(t)

    if amt >= H:
        ret = min(dp[amt], ret)

print(ret)


### FIXED CODE ###

H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]


max_magic = 0
for a, _ in magic:
    max_magic = max(max_magic, a)

amount = H + 1
dp = [0] * (amount + max_magic)
dp[0] = 0

ret = float('inf')

for amt in range(1, amount + max_magic):
    t = [dp[amt - a] + b for a, b in magic]
    dp[amt] = min(t)

    if amt >= H:
        ret = min(dp[amt], ret)

print(ret)
### BUGGY CODE ###

N = int(input())

Slist = {}
maxNum = 1
for i in range(N):
    S = input()
    if S in Slist.keys():
        Slist[S] += 1
        if Slist[S] > maxNum:
            maxNum = Slist[S]
    else:
        Slist[S] = 1

ans = []
for str in Slist.keys():
    if Slist[str] == maxNum:
        ans.append(str)

ans.sort()
for str in ans:
    print(str)

### FIXED CODE ###

# import sys
# input = sys.stdin.readline

N = int(input())

Slist = []
for i in range(N):
    Slist.append(input())
    # if S in Slist.keys():
    #     Slist[S] += 1
    #     if Slist[S] > maxNum:
    #         maxNum = Slist[S]
    # else:
    #     Slist[S] = 1
Slist.sort()

max_cnt = 1
cnt = 1
s_old = Slist[0]
max_Slist = []

for i in range(1,N):
    if Slist[i] == s_old:
        cnt += 1
    else:
        if cnt > max_cnt:
            max_cnt = cnt
            max_Slist = [s_old]
        elif cnt == max_cnt:
            max_Slist.append(s_old)
        s_old = Slist[i]
        cnt = 1

if Slist[N-1] == s_old:
    if cnt > max_cnt:
        max_Slist = [s_old]
    elif cnt == max_cnt:
        max_Slist.append(s_old)

for str in max_Slist:
    print(str)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

      
n,m = map(int, input().split())
p = [x-1 for x in list(map(int, input().split()))]
key = dict()
for k,v in enumerate(p):
  key[v] = k
Union = UnionFind(n)
for i in range(m):
  x,y = map(int, input().split())
  Union.union(x-1,y-1)
a = Union.all_group_members()
ans = 0
for i in a.values():
  x = set()
  for j in i:
    x.add(key[j])
  y = set(i)
  ans += len(x & y)
print(ans)

### FIXED CODE ###

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
    
    def all_group_members(self):
        return_list = [list() for i in range(n)]
        for i in range(n):
          return_list[self.find(i)].append(i)
        return return_list
      
      
n,m = map(int, input().split())
p = [x-1 for x in list(map(int, input().split()))]
key = dict()
for k,v in enumerate(p):
  key[v] = k
Union = UnionFind(n)
xy = [list(map(int, input().split())) for i in range(m)]
for x,y in xy:
  Union.union(x-1,y-1)
a = Union.all_group_members()
ans = 0
for i in a:
  x = set()
  for j in i:
    x.add(key[j])
  y = set(i)
  ans += len(x & y)
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
A= [input() for i in range(N)]
ans = 0
for i in range(N):
    j = i+1
    a = collections.Counter(A[i])
    while j < N:
        b = collections.Counter(A[j])
        if a==b:
            ans +=1
        j+=1
print(ans)

### FIXED CODE ###

n =int(input())

S=[]
ans = 0
count=1

for i in range(n):
    tmp=input()
    S.append("".join(sorted(tmp)))

S.sort()

for i in range(len(S)-1):
    if S[i] == S[i+1]:
        count+=1
    else:
        ans+=count*(count-1)/2
        count=1

ans+=count*(count-1)/2

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

H, W = map(int, input().split())
g = [str(input()) for _ in range(H)]
LW = [[0] * W for _ in range(H)]
LH = [[0] * W for _ in range(H)]
for h in range(H):
    cnt = 0
    for w in range(W):
        if g[h][w] == '.':
            cnt += 1
        else:
            for i in range(1, cnt+1):
                LW[h][w-i] = cnt
            LW[h][w] = 0
            cnt = 0
    else:
        for i in range(cnt):
            LW[h][w-i] = cnt
for w in range(W):
    cnt = 0
    for h in range(H):
        if g[h][w] == '.':
            cnt += 1
        else:
            for i in range(1, cnt+1):
                LH[h-i][w] = cnt
            LH[h][w] = 0
            cnt = 0
    else:
        for i in range(cnt):
            LH[h-i][w] = cnt
ans = 0
for h in range(H):
    for w in range(W):
        if g[h][w] != '#':
            ans = max(ans, LH[h][w] + LW[h][w] - 1)
print(ans)



### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    g = [str(input()) for _ in range(H)]
    LW = [[0] * W for _ in range(H)]
    LH = [[0] * W for _ in range(H)]
    for h in range(H):
        cnt = 0
        for w in range(W):
            if g[h][w] == '.':
                cnt += 1
            else:
                for i in range(1, cnt+1):
                    LW[h][w-i] = cnt
                LW[h][w] = 0
                cnt = 0
        else:
            for i in range(cnt):
                LW[h][w-i] = cnt
    for w in range(W):
        cnt = 0
        for h in range(H):
            if g[h][w] == '.':
                cnt += 1
            else:
                for i in range(1, cnt+1):
                    LH[h-i][w] = cnt
                LH[h][w] = 0
                cnt = 0
        else:
            for i in range(cnt):
                LH[h-i][w] = cnt
    ans = 0
    for h in range(H):
        for w in range(W):
            if g[h][w] != '#':
                ans = max(ans, LH[h][w] + LW[h][w] - 1)
    print(ans)
main()
### BUGGY CODE ###

L,R=map(int,input().split())
MOD=2019
for i in range(L,R):
    for j in range(i+1,R+1) :
        if (i*j)%2019 < MOD :
            MOD = (i*j)%2019
print (MOD)



### FIXED CODE ###

L,R=map(int,input().split())
M=2019
import sys
for i in range(L,R):
    for j in range(i+1,R+1) :
        if (i*j)%2019 < M :
            M = (i*j)%2019
            if M == 0:
                print(M)
                sys.exit()
print (M)
### BUGGY CODE ###

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

LRDi = []
for _ in range(M):
    a = list(map(int, input().split()))
    LRDi.append(a)

tree = [None] * (N + 1)

def parent(n):
    if tree[n] is None:
        return [n, 0]
    d = distance_to_root(n)
    p = parent(tree[n][0])
    tree[n][0] = p[0]
    tree[n][1] = d
    return tree[n]

def distance_to_root(n):
    if tree[n] is None:
        return 0
    d = distance_to_root(tree[n][0])
    return d + tree[n][1]

for l, r, d in LRDi:
    lp = parent(l)
    rp = parent(r)
    if lp[0] != rp[0]:
        rd = distance_to_root(r)
        tree[rp[0]] = [lp[0], lp[1] + d - rd]
    else:
        d1 = distance_to_root(l)
        d2 = distance_to_root(r)
        if d1 + d != d2:
            print("No")
            exit()

print("Yes")




### FIXED CODE ###

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

LRDi = []
for _ in range(M):
    a = list(map(int, input().split()))
    LRDi.append(a)

#tree = [None] * (N + 1)
tree = [[i, 0] for i in range(N + 1)]

def parent(n):
    p = n
    while tree[p][0] != p:
        p = tree[p][0]
    if p == n:
        return tree[n]
    if p == tree[n][0]:
        return tree[n]
    d = distance_to_root(n)
    tree[n][0] = p
    tree[n][1] = d
    return tree[n]

def distance_to_root(n):
    ret = 0
    nn = n
    while tree[nn][0] != nn:
        ret += tree[nn][1]
        nn = tree[nn][0]
    return ret

for l, r, d in LRDi:
    lp = parent(l)
    rp = parent(r)
    if lp[0] != rp[0]:
        rd = distance_to_root(r)
        tree[rp[0]] = [lp[0], lp[1] + d - rd]
    else:
        d1 = distance_to_root(l)
        d2 = distance_to_root(r)
        if d1 + d != d2:
            print("No")
            exit()

print("Yes")
### BUGGY CODE ###

#模範解答の通りにやってみる
N,K=map(int,input().split())
P=list(map(int,input().split()))
S=[]
if K==1:
	print((max(P)+1)/2)
elif N==K:
	print((sum(P)+N)/2)
else:
	for k in range(1,N+1):
		S.append(sum(P[0:k]))
	T=S[K-1]
	for n in range(0,N-K):
		if T<=S[n+K]-S[n]:
			T=S[n+K]-S[n]

	print((T+K)/2)


### FIXED CODE ###

#模範解答の通りにやってみる
N,K=map(int,input().split())
P=list(map(int,input().split()))
if K==1:
	print((max(P)+1)/2)
elif N==K:
	print((sum(P)+N)/2)
else:
	T=sum(P[0:(K)])
	S=sum(P[0:(K)])
	for k in range(0,N-K):
		S=S-P[k]+P[k+K]
		if T<=S:
			T=S
		else:
			continue
	print((T+K)/2)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [0 for i in range(N)]
B = [0 for i in range(N)]

for i in range(N):
  a,b = map(int, input().split())
  A[i] = a
  B[i] = b

ans = 0
count = 0
while(count < M):
  min_A = min(A)
  min_Ai = A.index(min_A)
  B_min = B[min_Ai]
  if count + B_min >= M:
    print(ans + min_A * (M - count))
    break
  else:
    ans += min_A * B_min
    count += B_min
    del A[min_Ai]
    del B[min_Ai]


### FIXED CODE ###

def unzip(li):
  return map(list, zip(*li))

N, M = map(int, input().split())
tmp_C = [0 for i in range(N)]

for i in range(N):
  a,b = map(int, input().split())
  tmp_C[i] = (a,b)
  
C = sorted(tmp_C)
A, B = unzip(C)
ans = 0
count = 0
cur = 0
while(count < M):
  min_A = A[cur]
  B_min = B[cur]
  if count + B_min >= M:
    print(ans + min_A * (M - count))
    break
  else:
    ans += min_A * B_min
    count += B_min
    cur += 1