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

#2分探索
#md/cで交点が定まらない時の対案
n,k = map(int, input().split( ))
m = [tuple(map(int, input().split( ))) for i in range(n)]
#そもそも設定はn枚すべて焼く必要はない
mx = 10**15
mn = 0
from math import sqrt
def solve(x1, y1, r1, x2, y2, r2):
    rr0 = (x2 - x1)**2 + (y2 - y1)**2
    xd = x2 - x1
    yd = y2 - y1
    rr1 = r1**2; rr2 = r2**2
    cv = (rr0 + rr1 - rr2)
    if max(r1,r2,sqrt(rr0))*2>r1+r2+sqrt(rr0):
        return (x1,y1),(x2,y2)
    sv = sqrt(4*rr0*rr1 - cv**2)
    return (
        (x1 + (cv*xd - sv*yd)/(2.*rr0), y1 + (cv*yd + sv*xd)/(2.*rr0)),
        (x1 + (cv*xd + sv*yd)/(2.*rr0), y1 + (cv*yd - sv*xd)/(2.*rr0)),
    )

#flag で breakしてたのが煩雑すぎて追えていなかったらしい
while mx-mn>10**(-10):
    md = (mx+mn)/2
    cnt = 0
    for i in range(n):##中心選ぶケースが抜けてる
        pi0,pi1 = m[i][0],m[i][1]
        tmp = 0
        for l in range(n):#kはすでに使っている変数
            if m[l][2]*sqrt(((pi0-m[l][0])**2) + ((pi1-m[l][1])**2))<=md+0.000000001:
                tmp += 1
        if cnt<tmp:
            cnt = tmp

    for i in range(n):
        for j in range(n):##range(i)だとi=0で止まって何もしない
            if i==j:
                continue
            p = solve(m[i][0],m[i][1],md/m[i][2], m[j][0],m[j][1],md/m[j][2])

            for pi in p:
                tmp = 0
                for l in range(n):#kはすでに使っている変数
                    if (((pi[0]-m[l][0])**2) + ((pi[1]-m[l][1])**2))**(1/2)<=md/m[l][2]+0.000000001:##ここで誤差認めなかったせいらしい
                        tmp += 1
                if cnt<tmp:
                    cnt = tmp
                
    if cnt>=k:
        mx = md
    else:
        mn = md
print(mx)


### FIXED CODE ###

#2分探索
#md/cで交点が定まらない時の対案
n,k = map(int, input().split( ))
m = [tuple(map(int, input().split( ))) for i in range(n)]
#そもそも設定はn枚すべて焼く必要はない
mx = 10**15
mn = 0
from math import sqrt
def solve(x1, y1, r1, x2, y2, r2):
    rr0 = (x2 - x1)**2 + (y2 - y1)**2
    xd = x2 - x1
    yd = y2 - y1
    rr1 = r1**2; rr2 = r2**2
    cv = (rr0 + rr1 - rr2)
    if max(r1,r2,sqrt(rr0))*2>r1+r2+sqrt(rr0):
        return (x1,y1),(x2,y2)
    sv = sqrt(4*rr0*rr1 - cv**2)
    return (
        (x1 + (cv*xd - sv*yd)/(2.*rr0), y1 + (cv*yd + sv*xd)/(2.*rr0)),
        (x1 + (cv*xd + sv*yd)/(2.*rr0), y1 + (cv*yd - sv*xd)/(2.*rr0)),
    )

#flag で breakしてたのが煩雑すぎて追えていなかったらしい
while mx-mn>10**(-6) and mx-mn>10**(-7)*mx:#mx大きい時に安易に設定すると到達しない？
    md = (mx+mn)/2
    cnt = 0
    for i in range(n):##中心選ぶケースが抜けてる
        pi0,pi1 = m[i][0],m[i][1]
        tmp = 0
        for l in range(n):#kはすでに使っている変数
            if m[l][2]*sqrt(((pi0-m[l][0])**2) + ((pi1-m[l][1])**2))<=md+0.000000001:
                tmp += 1
        if cnt<tmp:
            cnt = tmp

    for i in range(n):
        for j in range(i+1,n):##range(i)だとi=0で止まって何もしない

            p = solve(m[i][0],m[i][1],md/m[i][2], m[j][0],m[j][1],md/m[j][2])

            for pi in p:
                tmp = 0
                for l in range(n):#kはすでに使っている変数
                    if (((pi[0]-m[l][0])**2) + ((pi[1]-m[l][1])**2))**(1/2)<=md/m[l][2]+0.000000001:##ここで誤差認めなかったせいらしい
                        tmp += 1
                if cnt<tmp:
                    cnt = tmp

    if cnt>=k:
        mx = md
    else:
        mn = md
print(mx)
### BUGGY CODE ###

from heapq import heappop, heappush


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


n = int(input())
xd = [list(map(int, input().split())) for _ in range(n)]
mod = 998244353
INF = 10 ** 18

xx = []
for i, (x, d) in enumerate(xd, 1):
    xx.append([i, x, 0])
    xx.append([i, x + d - 0.5, 1])

xx.sort(key=lambda x: x[1])

adj = [[] for _ in range(n + 1)]
hp = [(INF, 0)]
uf = UnionFind(2 * (n + 1))

for i, x, remove in xx:
    if remove:
        uf.unite(0, i + n + 1)

    else:
        while uf.same(hp[0][1], hp[0][1] + n + 1):
            heappop(hp)

        px, pi = hp[0]
        adj[pi].append(i)

        uf.unite(0, i)
        heappush(hp, (-x, i))

stack = [0]
d = [-1] * (n + 1)
d[0] = 0
c = [[] for _ in range(n + 1)]
order = []
while stack:
    u = stack.pop()
    order.append(u)
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            c[u].append(v)
            stack.append(v)

dp = [1] * (n + 1)
for u in order[::-1]:
    for v in c[u]:
        dp[u] *= dp[v]
        dp[u] %= mod

    dp[u] += 1
    dp[u] %= mod

ans = dp[0] - 1
ans %= mod
print(ans)


### FIXED CODE ###

def main():
    n = int(input())
    xd = [map(int, input().split()) for _ in range(n)]
    mod = 998244353
    INF = 10 ** 10

    xx = [(x, x + d, i) for i, (x, d) in enumerate(xd, 1)]
    xx.sort()
    adj = [[] for _ in range(n + 1)]
    stack = [(INF, 0)]
    for l, r, i in xx:
        while stack[-1][0] <= l:
            stack.pop()

        ip = stack[-1][1]
        adj[ip].append(i)
        stack.append((r, i))

    stack2 = [0]
    d = [-1] * (n + 1)
    d[0] = 0
    c = [[] for _ in range(n + 1)]
    order = []
    while stack2:
        u = stack2.pop()
        order.append(u)
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                c[u].append(v)
                stack2.append(v)

    dp = [1] * (n + 1)
    for u in order[::-1]:
        for v in c[u]:
            dp[u] *= dp[v]
            dp[u] %= mod

        dp[u] += 1
        dp[u] %= mod

    ans = dp[0] - 1
    ans %= mod
    print(ans)


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

N, K = map(int, input().split())
a = tuple(map(int, input().split()))

def main():
    l = [0] * (K+1)
    for i in range(N):
        t = 0
        lt = l
        l = [0] * (K + 1)
        for j in range(K+1):
            if i == 0:
                if a[i] >= j:
                    l[j] = 1
            elif j == 0:
                t = 1
                l[j] = 1
            else:
                if j <= a[i]:
                    t += lt[j]
                else:
                    t += (lt[j] - lt[j - a[i] - 1])
                l[j] += t
    return l[-1] % (10 ** 9 + 7)
            
print(main())


### FIXED CODE ###

N, K = map(int, input().split())
a = tuple(map(int, input().split()))

def main():
    l = [1 if a[0] >= j else 0 for j in range(K+1)]
    lt= [0] * (K+1)
    s = a[0]
    for i in range(1,N):
        lt, l = l, lt
        s += a[i]
        l[0] = 1
        t = 1
        for j in range(1, a[i]+1):
                t += lt[j]
                l[j] = t
        for j in range(a[i]+1, min(K+1, s+1)):
                t += (lt[j] - lt[j - a[i] - 1])
                l[j] = t
    return l[-1] % (10 ** 9 + 7)
            
print(main())
### BUGGY CODE ###

 # -*- coding: utf-8 -*-

T = int(input())

for i in range(T):
	A, B, C, D = map(int, input().split())
	zaiko = A
	while True:
		zaiko -= B
		if zaiko < 0:
			print("No")
			break
		if zaiko <= C:
			zaiko += D
			if zaiko == A:
				print("Yes")
				break

### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

for _ in range(INT()):
    a, b, c, d = MAP()

    # そもそも無理
    if a < b or d < b:
        No()
        continue
    
    # b個減ってd個増える繰り返しなので、このgより細かく値が動くことはない
    g = gcd(b, d)

    # cより大きくてb未満が存在するかどうか
    mn = bisearch_min(-INF, INF, lambda m: a%g + g*m > c)
    mx = bisearch_max(-INF, INF, lambda m: a%g + g*m < b)
    if mn > mx:
        Yes()
    else:
        No()
### BUGGY CODE ###

n, m = map(int,input().split())
ans = 1
if abs(n-m) == 0:
    for i in range(1,n+1):
       ans *= i
    ans = 2*(ans**2)
    print(ans%(10**9+7))
    


elif abs(n-m) == 1:
    for i in range(1,min(n+1,m+1)):
        ans *= i
    ans = max(n,m)*(ans**2)
    print(ans%(10**9+7))


else:
    print(0)

### FIXED CODE ###

n, m = map(int,input().split())
ans = 1
if abs(n-m) == 0:
    for i in range(1,n+1):
       ans *= i
       ans = ans%(10**9+7)
    ans = 2*(ans**2)
    print(ans%(10**9+7))
    


elif abs(n-m) == 1:
    for i in range(1,min(n+1,m+1)):
        ans *= i
        ans = ans%(10**9+7)
    ans = max(n,m)*(ans**2)
    print(ans%(10**9+7))


else:
    print(0)
### BUGGY CODE ###

def main():
    s = input()[::-1]

    sum_of_digits = 0

    cnts = [0] * 2019

    cnts[0] = 1

    for i in range(len(s)):
        sum_of_digits += int(s[i]) * pow(10, i) % 2019
        sum_of_digits %= 2019
        cnts[sum_of_digits] += 1


    ans = 0

    for cnt in cnts:
        ans += cnt * (cnt - 1) // 2

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = input()[::-1]

    sum_of_digits = 0

    cnts = [0] * 2019

    cnts[0] = 1

    d = 1

    for i in range(len(s)):
        sum_of_digits += int(s[i]) * d
        d *= 10
        d %= 2019
        sum_of_digits %= 2019
        cnts[sum_of_digits] += 1


    ans = 0

    for cnt in cnts:
        ans += cnt * (cnt - 1) // 2

    print(ans)

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

k, s = map(int, input().split())

res = 0
for x in range(k+1):
    for y in range(min(k+1, s-x+1)):
        for z in range(min(k+1, s-x-y+1)):
            if x+y+z == s:
                res += 1

print(res)

### FIXED CODE ###

k, s = map(int, input().split())

res = 0
for x in range(k+1):
    for y in range(k+1):
        if x + y <= s:
            if x + y + k >= s:
                res += 1
        else:
            break

print(res)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
s = 1
for i in range(N):
    s = s * A[i]
    i += 1
if s > 10**18:
    print(-1)
else:
    print(s)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
s = 1
for i in range(N):
    if A[i] == 0:
        s = 0
        i += 1
if s == 0:
    print(0)
else:
    for i in range(N):
        s = s * A[i]
        if s > 10**18:
            break
        i += 1
    if s > 10**18:
        print(-1)
    else:
        print(s)
### BUGGY CODE ###


import itertools
 
N, M, R = map(int, input().split())
rs = map(int, input().split())
rs = list(map(lambda x:x-1 , rs))
ABCs = [list(map(int, input().split())) for i in range(M)]
 
d = [[10**6] * N for i in range(N)]
 
for abc in ABCs:
    d[abc[0]-1][abc[1]-1] = abc[2]
    d[abc[1]-1][abc[0]-1] = abc[2]
 
for i in range(N):
    for j in range(N):
        for k in range(N):
            d[j][k] = min(d[j][k], d[j][i] + d[i][k])
            
kyori = 0
ans = 10**6
narabi = list(itertools.permutations(rs,R))
for pt in narabi:
    for i in range(len(pt)-1):
        kyori += d[pt[i]][pt[i+1]]
    if kyori < ans:
        ans = kyori
    kyori = 0

print(ans)

            


### FIXED CODE ###

from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
ARSP = [[float('inf')] * (N+1) for i in range(N+1)]
for i in range(M):
    a, b, c = map(int, input().split())
    ARSP[a][b] = c
    ARSP[b][a] = c


def warshall_floyd(adj_array):
    for k in range(len(adj_array)):
        for i in range(len(adj_array)):
            for j in range(len(adj_array)):
                if adj_array[i][k] + adj_array[k][j] < adj_array[i][j]:
                    adj_array[i][j] = min(adj_array[i][j], adj_array[i][k] + adj_array[k][j])
    return adj_array


ARSP = warshall_floyd(ARSP)

# 訪れ方の全列挙(max 8! = 40320)
journey = list(permutations(r))

ans = float('inf')
for j in journey:
    cost = 0
    for i in range(1, R):
        if ARSP[j[i]][j[i-1]] == float('inf'):
            break
        cost += ARSP[j[i]][j[i-1]]
        if cost >= ans:
            break
    else:
        ans = cost

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

N = int(input())
graph=[[float("INF")]*(N+1) for _ in range(N+1)]
E ={i:[] for i in range(N+1)}
for i in range(N-1):
  a,b,c = [int(x) for x in input().split()]
  E[a].append([b,c])
  E[b].append([a,c])
Q,K = [int(x) for x in input().split()]
cost= [0]*(N+1)
stk=[[K,-1,0]]
while stk:
  v,p,c = stk.pop()
  if cost[v]!=0:
    continue
  cost[v]=c
  for i,j in E[v]:
    if i!=p:
      stk.append([i,v,c+j])
for i in range(Q):
  a,b = [int(x) for x in input().split()]
  print(cost[a]+cost[b])

### FIXED CODE ###

N = int(input())
E ={i:[] for i in range(N+1)}
for i in range(N-1):
  a,b,c = [int(x) for x in input().split()]
  E[a].append([b,c])
  E[b].append([a,c])
Q,K = [int(x) for x in input().split()]
cost= [0]*(N+1)
stk=[[K,-1,0]]
while stk:
  v,p,c = stk.pop()
  if cost[v]!=0:
    continue
  cost[v]=c
  for i,j in E[v]:
    if i!=p:
      stk.append([i,v,c+j])
for i in range(Q):
  a,b = [int(x) for x in input().split()]
  print(cost[a]+cost[b])
### BUGGY CODE ###

N = input()

ans = 0
N = int(N)
while N > 0:
  ans += N % 10
  N //= 10

if ans % 9 == 0:
  print("Yes")
else:
  print("No")



### FIXED CODE ###

N = input()

ans = 0
for i in range(len(N)):
  ans += int(N[i])

if ans % 9 == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

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

ans = []
numA = min([A, K])

for i in range(B + 1):
  if K - numA - i <= C:
    wa = numA - (K - numA - i)
    ans.append(wa)
            
print(max(ans))
        

### FIXED CODE ###

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

ans = []
numA = min([A, K])
numB = min([B, K - numA])
numC = K - numA - numB 

print(numA - numC)
### BUGGY CODE ###

from math import factorial
import collections

N = int(input())
A = input().split()
A = [int(x) for x in A]

L = collections.Counter(A)

c = 0
for i in range(1,N+1):
    n = L[i]
    if n >=2:
        c += factorial(n) // factorial(2) // factorial(n - 2)

for k in range(N):
    c1 = c
    x = A[k]
    n = L[x]
    if n >= 2:
        c1 -= factorial(n) // factorial(2) // factorial(n - 2)
        if n >= 3:
            c1 += factorial(n-1) // factorial(2) // factorial(n-3)
    print(c1)

### FIXED CODE ###

from math import factorial
import collections

N = int(input())
A = input().split()
A = [int(x) for x in A]

L = collections.Counter(A)

c = 0
for i in range(1,N+1):
    n = L[i]
    if n >=2:
        c += factorial(n) // factorial(2) // factorial(n - 2)

for k in range(N):
    c1 = c
    n = L[A[k]]
    if n >= 3:
        c1 -= n-1
    elif n == 2:
        c1 -= factorial(n) // factorial(2) // factorial(n-2)
    print(c1)
### BUGGY CODE ###

n = int(input())
s = input()
dp = [1] * n
mod = 10 ** 9 + 7
for ind, i in enumerate(s):
    dp2 = [0] * n
    if i == ">":
        s = 0
        for j in reversed(range(n-ind)):
            dp2[j] = s
            s += dp[j]
            s %= mod
    else:
        s = 0
        for j in range(n):
            s += dp[j]
            dp2[j] = s
            s %= mod
    dp = dp2
print(dp[0])
a = 0


### FIXED CODE ###

n = int(input())
s = input()
dp = [1] * n
mod = 10 ** 9 + 7
for ind, i in enumerate(s):
    dp2 = [0] * n
    if i == ">":
        s = 0
        for j in reversed(range(n-ind)):
            dp2[j] = s
            s += dp[j]
            s %= mod
    else:
        s = 0
        for j in range(n):
            s += dp[j]
            dp2[j] = s
            s %= mod
    dp = dp2
print(dp[0])
### BUGGY CODE ###

x,y = map(int,input().split())
t = 1
if x == y:
    print(-1)
else:
    while True:
        if (x * t) % y != 0:
            print(x * t)
            break
        t += 1


### FIXED CODE ###

x,y = map(int,input().split())
if x % y == 0:
    print(-1)
else:
    print(x)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

iNum = int(input())
naXY = np.zeros((iNum,2))
for iI in range(iNum):
  x, y = map(int, input().split())
  naXY[iI] = [x,y]
naXY0 = np.average(naXY, axis = 0) + np.random.rand(2) * 1e-3
fA = 1.0e-1
while fA > 1.0e-10:
  naP  = naXY - naXY0
  naR = np.einsum("ij, ij -> i", naP,naP)
  iImax = np.argmax(naR)
  #fR  = naR[iImax]**0.5
  naE = naP[iImax]
  naE/= np.dot(naE,naE)**0.5
  #print(iImax, naXY0, fR)
  #naB = np.einsum("ij, j->i", naP, naE)*2
  #naA = (naR - fR**2 ) / (naB - 1.0e-10 - fR)
  #fA  = np.min(naA[naB< - 1.0e-20])
  #print(iImax, fA, fR)
  #naXY0+=naE*fA
  naXY0+=naE*fA
  fA*=0.9998
print(naR[iImax]**0.5)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

iNum = int(input())
naXY = np.zeros((iNum,2))
for iI in range(iNum):
  x, y = map(int, input().split())
  naXY[iI] = [x,y]
naXY0 = np.average(naXY, axis = 0) + np.random.rand(2) * 1e-3
fA = 1.0e-1
while fA > 1.0e-10:
  naP  = naXY - naXY0
  naR = np.einsum("ij, ij -> i", naP,naP)
  iImax = np.argmax(naR)
  #fR  = naR[iImax]**0.5
  naE = naP[iImax]
  #naE/= np.dot(naE,naE)**0.5
  #print(iImax, naXY0, fR)
  #naB = np.einsum("ij, j->i", naP, naE)*2
  #naA = (naR - fR**2 ) / (naB - 1.0e-10 - fR)
  #fA  = np.min(naA[naB< - 1.0e-20])
  #print(iImax, fA, fR)
  #naXY0+=naE*fA
  naXY0+=naE*fA
  fA*=0.9998
print(naR[iImax]**0.5)
### BUGGY CODE ###

n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]

C = [card_set[1] for card_set in BC for j in range(card_set[0])]
A.extend(C)

A = sorted(A, reverse=True)
result = [A[i] for i in range(n)]
print(sum(result))

### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

maxi = n*2
extend = A.extend
[extend([ls[1]] * ls[0]) for ls in BC if len(A) <= maxi]
A.sort(reverse=True)

print(sum(A[:n]))
### BUGGY CODE ###

k,s = map(int,input().split())
cnt = 0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if (x+y+z)==s:
                cnt += 1

print(cnt)

### FIXED CODE ###

k,s = map(int,input().split())
cnt = 0
z = list(range(k+1))

for x in range(k+1):
    for y in range(k+1):
        m = s - x - y
        if 0 <= m & m <= k:
            cnt += 1

print(cnt)
### BUGGY CODE ###

H, N = map(int, input().split())
A = []
B = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
dp = [10000000000] * 10001
dp[0] = 0
for i in range(N):
    for j in range(10001):
        next = min(j + A[i], H)
        dp[next] = min(dp[next], dp[j] + B[i])
print(dp[H])


### FIXED CODE ###

H, N = map(int, input().split())
A = []
B = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
dp = [10000000000] * 10001
dp[0] = 0
for i in range(N):
    for j in range(10001):
        next = min(j + A[i], H)
        dp[next] = min(dp[next], dp[j] + B[i])
print(dp[H])
### BUGGY CODE ###

import numpy
h,w=map(int,input().split())
s=[list(input())for _ in range(h)]
score=[[0]*w for _ in range(h)]
ans=0
for i in range(h):
  tmp=0
  for j in range(w):
    if s[i][j]=="#":
      tmp=0
    else:
      tmp+=1
    score[i][j]+=tmp
for i in range(h):
  tmp=0
  for j in reversed(range(w)):
    if s[i][j]=="#":
      tmp=0
    else:
      tmp+=1
    score[i][j]+=tmp
for j in range(w):
  tmp=0
  for i in range(h):
    if s[i][j]=="#":
      tmp=0
    else:
      tmp+=1
    score[i][j]+=tmp
for j in range(w):
  tmp=0
  for i in reversed(range(h)):
    if s[i][j]=="#":
      tmp=0
    else:
      tmp+=1
    score[i][j]+=tmp-3
    ans=max(ans,score[i][j])
# print(score)
print(ans)

### FIXED CODE ###

h,w=map(int,input().split())
s=[list(input())for _ in range(h)]
score=[[0]*w for _ in range(h)]
ans=0
range_w=range(w)
range_h=range(h)
for i in range_h:
  tmp_1=0
  tmp_2=0
  for j in range_w:
    if s[i][j]=="#":
      tmp_1=0
    else:
      tmp_1+=1
    score[i][j]+=tmp_1
    
    if s[i][-j-1]=="#":
      tmp_2=0
    else:
      tmp_2+=1
    score[i][-j-1]+=tmp_2
    
for j in range_w:
  tmp_3=0
  tmp_4=0
  for i in range_h:
    if s[i][j]=="#":
      tmp_3=0
    else:
      tmp_3+=1
    score[i][j]+=tmp_3
    
    if s[-i-1][j]=="#":
      tmp_4=0
    else:
      tmp_4+=1
    score[-i-1][j]+=tmp_4-3
for i in range(h):
  for j in range(w):
    ans=max(ans,score[i][j])
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
h = [0] + h
dp = [float('inf')]*(N+1)
dp[0] = 0
dp[1] = 0
dp[2] = abs(h[2]-h[1])
for i in range(3,N+1):
  p = 1
  while p <= K and i-p > 0:
    dp[i] = min(dp[i],dp[i-p]+abs(h[i]-h[i-p]))
    p += 1
print(dp[N])

### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
h = [0] + h
dp = [float('inf')]*(N+1)
dp[0] = 0
dp[1] = 0
dp[2] = abs(h[2]-h[1])
for i in range(3,N+1):
  p = 1
  while p <= K and i-p > 0:
    dp[i] = min(dp[i],dp[i-p]+abs(h[i]-h[i-p]))
    p += 1
print(dp[N])
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(N)]
    AB.sort(key=lambda x: -x[1])
    M += 1
    w = [False] * M
    r = 0
    c = 0
    for a, b in AB:
        for i in reversed(range(M - a)):
            if w[i]:
                continue
            w[i] = True
            r += b
            c += 1
            break
    return r

print(main())


### FIXED CODE ###

import heapq

def main():
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(N)]
    AB.sort()
    AB.reverse()
    M += 1
    w = [False] * M
    q = []
    r = 0
    for i in range(1, M):
        while AB and AB[-1][0] <= i:
            heapq.heappush(q, -AB.pop()[1])
        if q:
            r += heapq.heappop(q)
    return -r

print(main())
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n = int(input())
A = [int(i) for i in input().split()]
d = {}
for a in A:
    if a in d:
        d.update({a: d.get(a) + 1})
    else:
        d.update({a: 1})

dr = {}
for x in A:
    if x not in dr:
        res = 0
        for item in d:
            y = d.get(item)
            if item == x:
                res += (y-1)*(y-2) // 2
            else:
                res += y*(y-1) // 2
        dr.update({x: res})

    print(dr.get(x))

### FIXED CODE ###

# -*- coding: utf-8 -*-

n = int(input())
A = [int(i) for i in input().split()]
d = {}

As = set(A)

for a in A:
    if a in d:
        d.update({a: d.get(a) + 1})
    else:
        d.update({a: 1})

summ = 0
for x in As:
    y = d.get(x)
    summ += y*(y-1) // 2

for a0 in A:
    print(summ - (d.get(a0)-1))