Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    order = dict()
    for i in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        order[(min(a-1, b-1), max(a-1, b-1))] = i
    K = 0
    for i in range(N): K = max(K, len(edge[i]))
    
    q = deque()
    col = [-1] * N
    col[0] = 0
    colE = [-1] * (N - 1)
    colPointer = 1
    for next in edge[0]: 
        q.append((0, next))
        col[next] = colPointer
        colE[order[(0, next)]] = colPointer
        colPointer += 1
    while q:
        parentNode, nowNode = q.popleft()
        par[nowNode] = parentNode
        colPointer = 1
        for nextNode in edge[nowNode]:
            if nextNode != parentNode:
                q.append((nowNode, nextNode))
                if colPointer == col[nowNode]: colPointer += 1
                col[nextNode] = colPointer
                colE[order[(min(nowNode, nextNode), max(nowNode, nextNode))]] = colPointer
                colPointer += 1

    print(K)
    for c in colE: print(c)

    return 0

if __name__ == "__main__":
    solve()

Fixed submission:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    order = dict()
    for i in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        order[(min(a-1, b-1), max(a-1, b-1))] = i
    K = 0
    for i in range(N): K = max(K, len(edge[i]))
    
    q = deque()
    col = [-1] * N
    col[0] = 0
    colE = [-1] * (N - 1)
    colPointer = 1
    for next in edge[0]: 
        q.append((0, next))
        col[next] = colPointer
        colE[order[(0, next)]] = colPointer
        colPointer += 1
    while q:
        parentNode, nowNode = q.popleft()
        colPointer = 1
        for nextNode in edge[nowNode]:
            if nextNode != parentNode:
                q.append((nowNode, nextNode))
                if colPointer == col[nowNode]: colPointer += 1
                col[nextNode] = colPointer
                colE[order[(min(nowNode, nextNode), max(nowNode, nextNode))]] = colPointer
                colPointer += 1

    print(K)
    for c in colE: print(c)

    return 0

if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

def solve():
    input = sys.stdin.readline
    N, T = map(int, input().split())
    food = [[int(i) for i in input().split()] for _ in range(N)]
    food.sort()
    DP = [[0 for _ in range(T)] for i in range(N + 1)]
    for i in range(N):
        a, b = food[i]
        for t in range(T):
            DP[i+1][t] = max(DP[i][t], DP[i+1][t])
            if t+a < T: DP[i+1][t+a] = max(DP[i+1][t+a], DP[i][t] + b)
    max_dish = 0
    for i in range(N):
        max_dish = max(max_dish, max(DP[i]) + food[i][1])
    print(max_dish)

    return 0

if __name__ == "__main__":
    solve()

Fixed submission:
import sys

def solve():
    input = sys.stdin.readline
    N, T = map(int, input().split())
    food = [[int(i) for i in input().split()] for _ in range(N)]
    food.sort()
    DP = [[0 for _ in range(T)] for i in range(N + 1)]
    for i in range(N):
        a, b = food[i]
        for t in range(T):
            DP[i+1][t] = max(DP[i][t], DP[i+1][t])
            if t+a < T: DP[i+1][t+a] = max(DP[i+1][t+a], DP[i][t] + b)
    max_dish = 0
    for i in range(N):
        max_dish = max(max_dish, max(DP[i]) + food[i][1])
    print(max_dish)

    return 0

if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Runtime Error):
import sys
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for i in range(N)]
    for i in range(1, N):
        Edge[i].append((0, i - 1))
    for _ in range(M):
        L, R, C = map(int, input().split())
        Edge[L-1].append((C, R-1))
    
    Dist = [-1] * N
    Q = []
    heapify(Q)
    heappush((0, 0))
    while Q:
        nowcost, nownode = heappop(Q)
        if Dist[nownode] == -1:
            Dist[nownode] = nowcost
            for addcost, nextnode in Edge[nownode]:
                if Dist[nownode] == -1:
                    heappush(Q, (nowcost + addcost, nextnode))
    print(Dist[N-1])

    return 0

if __name__ == "__main__":
    solve()

Fixed submission:
import sys
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for i in range(N)]
    for i in range(1, N):
        Edge[i].append((0, i - 1))
    for _ in range(M):
        L, R, C = map(int, input().split())
        Edge[L-1].append((C, R-1))
    
    Dist = [-1] * N
    Q = []
    heapify(Q)
    heappush(Q, (0, 0))
    while Q:
        nowcost, nownode = heappop(Q)
        if Dist[nownode] == -1:
            Dist[nownode] = nowcost
            for addcost, nextnode in Edge[nownode]:
                if Dist[nextnode] == -1:
                    heappush(Q, (nowcost + addcost, nextnode))
    print(Dist[N-1])

    return 0

if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Runtime Error):
import sys
import math

def solve():
    input = sys.stdin.readline
    a, b, x = map(int, input().split())
    if b * a * a == x: print(0)
    elif x >= 0.5 * b * a * a: #傾きが浅い
        x /= a
        ans = 2 * (total - x) / a
        print(math.degrees(math.atan(ans / a)))
    else: #傾きが大きい
        x /= a
        ans = 2 * x / b
        print(math.degrees(math.atan(b / ans)))
    return 0

if __name__ == "__main__":
    solve()

Fixed submission:
import sys
import math

def solve():
    input = sys.stdin.readline
    a, b, x = map(int, input().split())
    total = b * a
    if b * a * a == x: print(0)
    elif x >= 0.5 * b * a * a: #傾きが浅い
        x /= a
        ans = 2 * (total - x) / a
        print(math.degrees(math.atan(ans / a)))
    else: #傾きが大きい
        x /= a
        ans = 2 * x / b
        print(math.degrees(math.atan(b / ans)))
    return 0

if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    F = [int(f) for f in input().split()]
    A.sort(reverse = True)
    F.sort()
    low, high = -1, 10 ** 13
    while high - low > 1:
        mid = (low + high) // 2
        count = 0
        for i in range(N):
            counterF = mid // F[i] 
            if counterF < A[i]: count += A[i] - counterF
        if count <= K: high = mid
        else: low = mid
    print(high)
         
    return 0

if __name__ == "__main__":
    solve()

Fixed submission:
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    F = [int(f) for f in input().split()]
    A.sort(reverse = True)
    F.sort()
    low, high = -1, 10 ** 12 + 1
    while high - low > 1:
        mid = (low + high) // 2
        count = 0
        for i in range(N):
            if A[i] * F[i] > mid: count += A[i] - (mid // F[i])
        if count > K: low = mid
        else: high = mid
    print(high)

    return 0

if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from bisect import bisect_left


def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    F = [int(f) for f in input().split()]
    A.sort(reverse = True)
    F.sort()
    low, high = -1, 10 ** 12 + 1
    while high - low > 1:
        mid = (low + high) // 2
        count = 0
        for i in range(N):
            if A[i] * F[i] > mid: count += A[i] - (mid // F[i])
        if count > K: low = mid
        else: high = mid
    print(high)

    return 0

if __name__ == "__main__":
    solve()

Fixed submission:
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    F = [int(f) for f in input().split()]
    A.sort(reverse = True)
    F.sort()
    low, high = -1, 10 ** 12 + 1
    while high - low > 1:
        mid = (low + high) // 2
        count = 0
        for i in range(N):
            if A[i] * F[i] > mid: count += A[i] - (mid // F[i])
        if count > K: low = mid
        else: high = mid
    print(high)

    return 0

if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Runtime Error):
import sys

def solve():
	input=sys.stdin.readline
	n, m, l = map(int, input().split())
	edge = [[] for _ in range(n)]
	for _ in range(m):
		a, b, c = map(int, input().split())
		if c <= l:
			edge[a-1].append((c, b-1))
			edge[b-1].append((c, a-1))
	inf = 10 ** 20
	dist = [[inf for _ in range(n)]for i in range(n)]
	for i in range(n):
		dist[i][i]=0
		for c, b in edge[i]:
			dist[i][b]=c
			
	for k in range(n):
		for i in range(n):
			for j in range(n):
				dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
				
	dist2 = [[n+50 for j in range(n)] for i in range(n)]
	for i in range(n):
		dist2[i][i] = 0
		for j in range(i+1, n):
			if dist[i][j] <= l:
				dist2[i][j] = 1
				dist2[j][i] = 1
	for k in range(n):
		for i in range(n):
			for j in range(n):
				dist2[i][j] = min(dist2[i][k] + dist2[k][j])
	q = int(input())		
	for i in range(q):
		s, t = map(int, input().split())
		print(dist2[s-1][t-1] - 1)
	return 0
	
if __name__ == '__main__':
	solve()

Fixed submission:
import sys

def solve():
	input=sys.stdin.readline
	n, m, l = map(int, input().split())
	edge = [[] for _ in range(n)]
	for _ in range(m):
		a, b, c = map(int, input().split())
		if c <= l:
			edge[a-1].append((c, b-1))
			edge[b-1].append((c, a-1))
	inf = 10 ** 20
	dist = [[inf for _ in range(n)]for i in range(n)]
	for i in range(n):
		dist[i][i]=0
		for c, b in edge[i]:
			dist[i][b]=c
			
	for k in range(n):
		for i in range(n):
			for j in range(n):
				dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
				
	dist2 = [[n+50 for j in range(n)] for i in range(n)]
	for i in range(n):
		dist2[i][i] = 0
		for j in range(i+1, n):
			if dist[i][j] <= l:
				dist2[i][j] = 1
				dist2[j][i] = 1
	for k in range(n):
		for i in range(n):
			for j in range(n):
				dist2[i][j] = min(dist2[i][k] + dist2[k][j], dist2[i][j])
	q = int(input())		
	for i in range(q):
		s, t = map(int, input().split())
		print(dist2[s-1][t-1] - 1 if dist2[s-1][t-1] < n+50 else -1)
	return 0
	
if __name__ == '__main__':
	solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys, collections

def dfs(i, c, col, edge):
    col[i] = c
    for next_node in edge[i]:
        if col[next_node] == c: return False
        if col[next_node] == 0 and dfs(next_node, -c, col, edge) == False: return False

    return True

def solve():
    N = int(input())
    edge = dict()
    col = dict()
    for i in range(N): 
        edge[i] = set()
        col[i] = 0
        s = input()
        for j in range(N):
            if s[j] == "1": edge[i] |= {j}

    is_bipartite = dfs(0, 1, col, edge)
    if not is_bipartite: print(-1)
    else:
        INF = 10 ** 15
        dist = [[INF for j in range(N)] for i in range(N)]
        for i in range(N):
            for j in range(N):
                if i == j: dist[i][j] = 0
                elif j in edge[i]: dist[i][j] = 1

        for k in range(N):
            for i in range(N):
                for j in range(N): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

        ans = -1
        for i in range(N):
            for j in range(N):
                if dist[i][j] < INF: ans = max(ans, dist[i][j])
        print(ans + 1)

    

    return 0

if __name__ == "__main__":
    solve()


Fixed submission:
import sys, collections

def dfs(i, c, col, edge):
    col[i] = c
    for next_node in edge[i]:
        if col[next_node] == c: return False
        if col[next_node] == 0 and dfs(next_node, -c, col, edge) == False: return False

    return True

def solve():
    N = int(input())
    edge = dict()
    col = dict()
    for i in range(N): 
        edge[i] = set()
        col[i] = 0
        s = input()
        for j in range(N):
            if s[j] == "1": edge[i] |= {j}

    is_bipartite = dfs(0, 1, col, edge)
    if not is_bipartite: print(-1)
    else:
        INF = 10 ** 15
        dist = [[INF for j in range(N)] for i in range(N)]
        for i in range(N):
            for j in range(N):
                if i == j: dist[i][j] = 0
                elif j in edge[i]: dist[i][j] = 1

        for k in range(N):
            for i in range(N):
                for j in range(N): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

        ans = -1
        for i in range(N):
            for j in range(N):
                if dist[i][j] < INF: ans = max(ans, dist[i][j])
        print(ans + 1)

    

    return 0

if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())
print(max([A + b, A - B, A * B]))

Fixed submission:
A, B = map(int, input().split())
l = [A + B, A - B, A * B]
print(max(l))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque
import heapq

def solve():
    input = sys.stdin.readline
    N, M, P = map(int, input().split())
    graph = [None for i in range(M)]
    for i in range(M):
        a, b, c = map(int, input().split())
        graph[i] = (a - 1, b - 1, P - c)

    gain = [10 ** 20 for i in range(N)]
    gain[0] = 0
    
    for i in range(N):
        update = False
        for efrom, eto, ecost in graph:
            if gain[efrom] < 10 ** 20 and gain[eto] > gain[efrom] + ecost:
                gain[eto] = gain[efrom] + ecost
                update = True
        if not update:
            print(max(-gain[N-1], 0))
            break
    else:
        possible_min = gain[N-1]
        for i in range(N):
            for efrom, eto, ecost in graph:
                if gain[efrom] < 10 ** 20 and gain[eto] > gain[efrom] + ecost:
                    gain[eto] = gain[efrom] + ecost

        if gain[N-1] == possible_min: print(max(-gain[N-1], 0))
        else: print(-1)

    return 0

if __name__ == "__main__":
    solve()

Fixed submission:
import sys
from collections import deque
import heapq

def solve():
    input = sys.stdin.readline
    N, M, P = map(int, input().split())
    graph = [None for i in range(M)]
    for i in range(M):
        a, b, c = map(int, input().split())
        graph[i] = (a - 1, b - 1, P - c)

    gain = [10 ** 20 for i in range(N)]
    gain[0] = 0
    
    for i in range(N):
        update = False
        for efrom, eto, ecost in graph:
            if gain[efrom] < 10 ** 20 and gain[eto] > gain[efrom] + ecost:
                gain[eto] = gain[efrom] + ecost
                update = True
        if not update:
            print(max(-gain[N-1], 0))
            break
    else:
        possible_min = gain[N-1]
        for i in range(N):
            for efrom, eto, ecost in graph:
                if gain[efrom] < 10 ** 20 and gain[eto] > gain[efrom] + ecost:
                    gain[eto] = gain[efrom] + ecost

        if gain[N-1] == possible_min: print(max(-gain[N-1], 0))
        else: print(-1)

    return 0

if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

def solve():
    S = input()
    mod = 7 + 10 ** 9
    DP = [[0 for _ in range(13)] for _ in range(len(S))]
    if S[0] == "?":
        for i in range(10): DP[0][i] = 1
    else: DP[0][int(S[0])] = 1

    for i in range(1, len(S)):
        if S[i] == "?":
            for j in range(13):
                for k in range(10):
                    DP[i][(j * 10 + k) % 13] += DP[i-1][j]
                    DP[i][(j * 10 + k) % 13] %= mod
        else:
            k = int(S[i])
            for j in range(13):
                DP[i][(j * 10 + k) % 13] += DP[i-1][j]
                DP[i][(j * 10 + k) % 13] %= mod
    print(DP[len(S) - 1][5])

    return 0

if __name__ == "__main__":
    solve()

Fixed submission:
import sys

def solve():
    S = input()
    mod = 7 + 10 ** 9
    DP = [[0 for _ in range(13)] for _ in range(len(S))]
    if S[0] == "?":
        for i in range(10): DP[0][i] = 1
    else: DP[0][int(S[0])] = 1

    for i in range(1, len(S)):
        if S[i] == "?":
            for j in range(13):
                for k in range(10):
                    DP[i][(j * 10 + k) % 13] += DP[i-1][j]
                    DP[i][(j * 10 + k) % 13] %= mod
        else:
            k = int(S[i])
            for j in range(13):
                DP[i][(j * 10 + k) % 13] += DP[i-1][j]
                DP[i][(j * 10 + k) % 13] %= mod
    print(DP[len(S) - 1][5])

    return 0

if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys, collections

def count(q, ans):
    unused = collections.deque()
    ans += 1
    num = -1
    while q:
        n = q.popleft()
        if n <= num:
            unused.append(n)
        else:
            num = n
    return unused, ans

def solve():
    input = sys.stdin.readline
    N = int(input())
    col = 0
    q = collections.deque()
    for _ in range(N):
        q.append(int(input()))

    while q:
        q, col = count(q, col)

    print(col)
    return 0

if __name__ == "__main__":
    solve()

Fixed submission:
import sys
from bisect import bisect_right, bisect_left

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(input()) for _ in range(N)]
    col = [1] * N
    col[0] = -A[0]
    for a in A[1:]:
        index = bisect_right(col, -a)
        col[index] = -a
        #print(col, index)
    ans = bisect_right(col, 0)
    print(ans)

    return 0

if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Runtime Error):
import sys, collections
sys.setrecursionlimit(10000000)

def comb(n, r, fact, revfact, mod):
    return (fact[n] * revfact[n-r] * revfact[r]) % mod

def dfs(now, edge, visited, mod, N, fact, revfact):
    visited[now] = True
    son = 0
    ans = 1
    for next in edge[now]:
        if not visited[next]:
            son += 1
            ans *= dfs(next, edge, visited, mod, N, fact, revfact)
            ans %= mod
    if son == 0: return 1
    else:
        ans *= comb(N-2, son, fact, revfact, mod)
        ans %= mod
        return ans

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    edge = [[] for i in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    mod = 7 + 10 ** 9

    fact = [1] * (K + 1)
    for i in range(2, K+1):
        fact[i] = (i * fact[i-1]) % mod
    revfact = [1] * (K+1)
    revfact[K] = pow(fact[K], mod - 2, mod)
    for i in reversed(range(1, K)):
        revfact[i] = ((i+1) * revfact[i+1]) % mod

    visited = [False] * N
    visited[0] = True
    ans = 1
    son = 0
    for next in edge[0]:
        son += 1
        ans *= dfs(next, edge, visited, mod, K, fact, revfact)
        ans %= mod
    ans *= (comb(K-1, son, fact, revfact, mod) * K) % mod
    ans %= mod

    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Fixed submission:
import sys, collections
sys.setrecursionlimit(10000000)

def permutation(k, r, fact, revfact, mod):
    return (fact[k] * revfact[k-r]) % mod

def dfs(now, parent, edge, mod, K, fact, revfact):
    son = 0
    ans = 1
    for next in edge[now]:
        if next != parent:
            son += 1
            ans *= dfs(next, now, edge, mod, K, fact, revfact)
            ans %= mod
    if K-2 < son: ans = 0
    elif son > 0:
        ans *= permutation(K-2, son, fact, revfact, mod)
        ans %= mod
    return ans
    

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    edge = [[] for i in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    mod = 7 + 10 ** 9

    fact = [1] * (K + 1)
    for i in range(2, K+1):
        fact[i] = (i * fact[i-1]) % mod
    revfact = [1] * (K+1)
    revfact[K] = pow(fact[K], mod - 2, mod)
    for i in reversed(range(1, K)):
        revfact[i] = ((i+1) * revfact[i+1]) % mod

    ans = K
    son = 0
    for next in edge[0]:
        son += 1
        ans *= dfs(next, 0, edge, mod, K, fact, revfact)
        ans %= mod
    ans *= permutation(K-1, son, fact, revfact, mod)
    ans %= mod

    print(ans)
    return 0

if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

def solve():
    input = sys.stdin.readline
    mod = 7 + 10 ** 9
    N, M = map(int, input().split())
    S = [int(s) for s in input().split()]
    T = [int(t) for t in input().split()]

    DP = [[0 for j in range(M+1)] for i in range(N + 1)]
    DP[0] = [1] * (M + 1)
    for i in range(1, N + 1): DP[i][0] = 1
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                DP[i+1][j+1] = (DP[i+1][j] + DP[i][j+1]) % mod
            else: 
                DP[i+1][j+1] = (DP[i+1][j] + DP[i][j+1] - DP[i][j]) % mod
    print(DP[N][M])
    return

if __name__ == "__main__":
    solve()

Fixed submission:
import sys

def solve():
    input = sys.stdin.readline
    mod = 7 + 10 ** 9
    N, M = map(int, input().split())
    S = [int(s) for s in input().split()]
    T = [int(t) for t in input().split()]

    DP = [[0 for j in range(M+1)] for i in range(N + 1)]
    DP[0] = [1] * (M + 1)
    for i in range(1, N + 1): DP[i][0] = 1
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                DP[i+1][j+1] = (DP[i+1][j] + DP[i][j+1]) % mod
            else: 
                DP[i+1][j+1] = (DP[i+1][j] + DP[i][j+1] - DP[i][j]) % mod
    print(DP[N][M])
    return

if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Runtime Error):
import sys
from operator import itemgetter

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    change = [[int(i) for i in input().split()] for _ in range(M)]
    change.sort(key = itemgetter(1), reverse = True)
    ai = 0
    for i in range(M):
        cb, c = change[i]
        if c < A[ai] or ai >= N: break
        for _ in range(cb):
            if ai >= N: break
            if A[ai] <= c:
                A[ai] = c
                ai += 1
            else: break
    print(sum(A))
    return 0

if __name__ == "__main__":
    solve()

Fixed submission:
import sys, math, collections, heapq, itertools

F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    N, M = map(int, line_input())
    A = [int(a) for a in line_input()]
    change = [None] * M
    for i in range(M):
        b, c = map(int, line_input())
        change[i] = [c, b]
    A.sort()
    change.sort(reverse = True)

    sum = 0
    index = 0
    for c, b in change:
        bleft = b
        while bleft > 0:
            if c > A[index]:
                sum += c
                index += 1
                bleft -= 1
                if index == N: break
            else: break
        if index == N: break
    if index < N:
        for i in range(index, N):
            sum += A[i]
    print(sum)

    return 0
  
if __name__ == "__main__":
    solve()