Harryxun/stf_run huggingface dataset:
H, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

inf = 10 ** 10
DP = [[inf] * (H + 1) for _ in range(N)]

for i in range(N):
  a, b = AB[i]
  for j in range(1, a + 1):
    if i == 0:
      DP[i][j] = b
    else:
      DP[i][j] = min(DP[i - 1][j], b)
  for j in range(a + 1, H + 1):
    if i == 0:
      DP[i][j] = DP[i][j - a] + b
    else:
      DP[i][j] = min(DP[i - 1][j], DP[i][j - a] + b)

print(DP[-1][H])



### FIXED CODE ###

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

inf = 10 ** 10
DP = [[inf] * (H + 1) for _ in range(N)]

for i in range(N):
  a, b = AB[i]
  if a >= H:
    for j in range(H + 1):
      if i == 0:
        DP[i][j] = b
      else:
        DP[i][j] = min(DP[i - 1][j], b)
    continue
  for j in range(1, a + 1):
    if i == 0:
      DP[i][j] = b
    else:
      DP[i][j] = min(DP[i - 1][j], b)
  for j in range(a + 1, H + 1):
    if i == 0:
      DP[i][j] = DP[i][j - a] + b
    else:
      DP[i][j] = min(DP[i - 1][j], DP[i][j - a] + b)

print(DP[-1][H])
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
cnt={}
for i in range(n):
  for j in range(n):
    if i==j:
      continue
    p=arr[i][0]-arr[j][0]
    q=arr[i][1]-arr[j][1]
    if (p,q) not in cnt:
      cnt[(p,q)]=1
    else:
      cnt[(p,q)]+=1
ans=n-max(cnt.values())
print(ans)

### FIXED CODE ###

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
arr=sorted(arr,key=lambda x:x[1])
arr=sorted(arr,key=lambda x:x[0])
ans=n
for i in range(n):
  for j in range(i+1,n):
    p,q=arr[j][0]-arr[i][0],arr[j][1]-arr[i][1]
    cnt=0
    flag=[0]*n
    for k in range(n):
      if flag[k]==1:
        continue
      flag[k]=1
      a,b=arr[k][0],arr[k][1]
      while 1:
        for l in range(n):
          if flag[l]==1:
            continue
          if a+p==arr[l][0] and b+q==arr[l][1]:
            flag[l]=1
            a=arr[l][0]
            b=arr[l][1]
            break
        else:
          break
      cnt+=1
    ans=min(ans,cnt)
print(ans)
n=input()
list=[]
for i in range(int(n)):
    a = input()
    list.append(int(a))
count=0
flag=0

while True:
    for i in range(int(n)):
        if(list[i]%2 != 0):
            flag += 1
    if(flag==1):
        break
        
    for i in range(int(n)):
        list[i] = list[i]/2
    count += 1
    
print(count)

### FIXED CODE ###

n=input()
n=int(n)

b = [int(e) for e in input().split()]
count=0
flag=0

#print(b[0])

while True:
    for i in range(n):
        if(b[i]%2 != 0):
            flag=1
            break
    if(flag==1):
        break
    count += 1
    for i in range(n):
        b[i]=b[i]/2

print(count)
from collections import defaultdict, deque
import sys
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    AB = sorted(AB, key=lambda it: it[1])

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    # print("ARR", ARR)

    res = 0
    q = []

    def merge(a, b, m):
        m = min(m, len(a) + len(b))
        res = [0] * m
        ia = len(a) - 1
        ib = len(b) - 1
        for i in range(m):
            j = m - 1 - i
            if a[ia] > b[ib]:
                res[j] = a[ia]
                ia -= 1
                if ia < 0:
                    while j >= 0:
                        res[j] = b[ib]
                        ib -= 1
                        j -= 1
                    return res
            else:
                res[j] = b[ib]
                ib -= 1
                if ib < 0:
                    while j >= 0:
                        res[j] = a[ia]
                        ia -= 1
                        j -= 1
                    return res
        return res

    for i in range(1, M + 1):
        current = ARR[i]
        if len(current) != 0:
            if len(q) != 0:
                if current[-1] > q[-1]:
                    res += current.pop()
                else:
                    res += q.pop()
            else:
                res += current.pop()
            # q = sorted(q + current)
            q = merge(q, current, M - i)
            # q = q[-(M - i):]
        else:
            if len(q) != 0:
                res += q.pop()
            else:
                pass
        # q += current
        # q = sorted(q)
        # # print(q)
        # if len(q) != 0:
        #     mm = q.pop()
        #     res += mm
        # q = q[-(M - i):]
    print(res)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, deque
import sys
import heapq
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    # AB = sorted(AB, key=lambda it: it[1])

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    # print("ARR", ARR)

    res = 0
    q = []
    for i in range(1, M + 1):
        current = ARR[i]
        for a in current:
            heapq.heappush(q, -a)
        if len(q) != 0:
            res -= heapq.heappop(q)
    print(res)


if __name__ == '__main__':
    main()
N = int(input())

input_list = []

for i in range(N):
  input_list.append(int(input)) 
  
input_list.sort()

input_list[-1] = int(input_list[-1] / 2)

ans = 0
for i in input_list:
  ans += i
  
print(ans)

### FIXED CODE ###

N = int(input())
 
input_list = []
 
for i in range(N):
  input_list.append(int(input())) 
  
input_list.sort()
 
input_list[-1] = int(input_list[-1] / 2)
 
ans = 0
for i in input_list:
  ans += i
  
print(ans)
import sys
import math

def decide_move(x,y,tile,check):
	if tile == '<':
		x -= 1
		check[x][y] += 1
		return x,y,check
	elif tile == '>':
		x += 1
		check[x][y] += 1
		return x,y,check
	elif tile == '^':
		y -= 1
		check[x][y] += 1
		return x,y,check
	else:
		y += 1
		check[x][y] += 1
		return x,y,check


while True:
	h,w = map(int,input().split())
	if h == 0:
		break
	tile_map = []
	for i in range(h):
		tile_map.append(input())
	check =[[0 for i in range(w)]for j in range(h)]
	check[0][0] = 1
	x = 0
	y = 0
	status = 0

	while True:
		if tile_map[x][y] == '.':
			status = 1
			print(y,x)
			break
		x,y,check = decide_move(x,y,tile_map[x][y],check)
		if check[x][y] > 1:
			status = 1
			print('LOOP')
			break

### FIXED CODE ###

import sys
import math

def decide_move(x,y,tile,check):
	if tile == '<':
		y -= 1
		check[x][y] += 1
		return x,y,check
	elif tile == '>':
		y += 1
		check[x][y] += 1
		return x,y,check
	elif tile == '^':
		x -= 1
		check[x][y] += 1
		return x,y,check
	else:
		x += 1
		check[x][y] += 1
		return x,y,check


while True:
	h,w = map(int,input().split())
	if h == 0:
		break
	tile_map = []
	for i in range(h):
		tile_map.append(input())
	check =[[0 for i in range(w)]for j in range(h)]
	check[0][0] = 1
	x = 0
	y = 0
	status = 0

	while True:
		if tile_map[x][y] == '.':
			status = 1
			print(y,x)
			break
		x,y,check = decide_move(x,y,tile_map[x][y],check)
		if check[x][y] > 1:
			status = 1
			print('LOOP')
			break
#! /usr/bin/env python
#-*- coding: utf-8 -*-

''' ?????????????????? '''

# O(n^2)


def bubble_sort(A, N):
    swap_num = 0  # ?????????????????°

    for i in range(N - 1):
        for j in range(N - 1, i, -1):
            if A[j] < A[j - 1]:
                # swap
                temp = A[j]
                A[j] = A[j - 1]
                A[j - 1] = temp
                swap_num += 1

    return (A, swap_num)


if __name__ == "__main__":
    N = input()
    A = list(map(int, input().split()))
    # A = [5, 2, 4, 6, 1, 3]
    # N = len(A)
    array_sorted, swap_num = bubble_sort(A, N)
    print(' '.join(map(str, array_sorted)))
    print(swap_num)

### FIXED CODE ###

#! /usr/bin/env python
#-*- coding: utf-8 -*-

''' ?????????????????? '''

# O(n^2)


def bubble_sort(A, N):
    swap_num = 0  # ?????????????????°

    for i in range(N - 1):
        for j in range(N - 1, i, -1):
            if A[j] < A[j - 1]:
                # swap
                temp = A[j]
                A[j] = A[j - 1]
                A[j - 1] = temp
                swap_num += 1

    return (A, swap_num)


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    # A = [5, 2, 4, 6, 1, 3]
    # N = len(A)
    array_sorted, swap_num = bubble_sort(A, N)
    print(' '.join(map(str, array_sorted)))
    print(swap_num)
H, W = map(int, input().split())
a = []

for i in range(H):
    a.append([int(x) for x in input().split()])

n = 0
ans = []
for y in range(H):
    if y % 2 == 0:
        for x in range(W - 1):
            if a[y][x] & 1:
                n += 1
                ans.append("{} {} {} {}".format(y + 1, x + 1, y + 1, x + 2))
                print(y + 1, x + 1, y + 1, x + 2)
        if y != H - 1 and a[y][W - 1] & 1:
            n += 1
            ans.append("{} {} {} {}".format(y + 1, W, y + 2, x + W))

    else:
        for x in range(W - 1, 0, -1):
            if a[y][x] & 1:
                n += 1
                ans.append("{} {} {} {}".format(y + 1, x + 1, y + 1, x))
        if y != H - 1 and a[y][0] & 1:
            n += 1
            ans.append("{} {} {} {}".format(y + 1, x + 1, y + 2, x + 1))

print(n)
print("\n".join(ans))

### FIXED CODE ###

def main():
    ans, a = [], []
    H, W = map(int, input().split())

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

    x, y, dx = 0, 0, 1

    while True:
        nx, ny = x, y
        if x+dx < 0 or W <= x+dx:
            nx = x
            ny = y+1 
            dx *= -1
        else:
            nx = x+dx
            ny = y

        if H <= ny:
            break

        if a[y][x] % 2 == 1:
            a[y][x] -= 1
            a[ny][nx] += 1
            ans += [str(y+1) + " " + str(x+1) + " " + str(ny+1) + " " + str(nx+1)]
        x, y = nx, ny

    print (len(ans))

    for i in ans:
        print (i)

main()
n = int(input())
f = [list(map(int,input().split())) for i in range(n)]
p = [list(map(int,input().split())) for i in range(n)]

s = [list(map(int,bin(x)[2:].zfill(10))) for x in range(2**10)]
s.pop(0)
c = 0
ans = 0
max = -10000000
for k in range(2**10-1):
    for i in range(n):
        for j in range(10):
            c += f[i][j]*s[k][j]
        ans += p[i][c+1]
        c=0
    if ans > max:
        max = ans
    ans = 0
print(max)


### FIXED CODE ###

n = int(input())
f = [list(map(int,input().split())) for i in range(n)]
p = [list(map(int,input().split())) for i in range(n)]

s = [list(map(int,bin(x)[2:].zfill(10))) for x in range(1,2**10)]
c = 0
ans = 0
max = -1000000000
for k in range(2**10-1):
    for i in range(n):
        for j in range(10):
            c += f[i][j]*s[k][j]
        ans += p[i][c]
        c=0
    if ans > max:
        max = ans
    ans = 0
print(max)
S = input()
flag = False
for i in range(26):
    c = chr(ord('a')+i)
    if c not in S:
        print(c)
        flag = True
        break
if !flag:
    print('None')

### FIXED CODE ###

S = input()
flag = False
for i in range(26):
    c = chr(ord('a')+i)
    if c not in S:
        print(c)
        flag = True
        break
if flag == False:
    print('None')
import fractions as fr
k = int(input())
ans = (k+1)*k//2
tttt = [[0]*(k+1) for _ in range(k+1)]
for i in range(1, k+1):
  for j in range(1, k+1):
    if i == j:
      continue
    else:
      if tttt[i][j] != 0:
        g = tttt[i][j]
        ans += 3*g
      else:
        g = fr.gcd(i,j)
        tttt[i][j] = g
        tttt[j][i] = g
        ans += 3*g
for i in range(1, k-1):
  for j in range(i+1, k):
    for l in range(j+1, k+1):
      temp = tttt[i][j]
      temp2 = tttt[temp][l]
      ans+= 6*tee
print(ans)

### FIXED CODE ###

import fractions as fr
k = int(input())
ans = (k+1)*k//2
tttt = [[0]*(k+1) for _ in range(k+1)]
for i in range(1, k+1):
  for j in range(1, k+1):
    if i == j:
      continue
    else:
      if tttt[i][j] != 0:
        g = tttt[i][j]
        ans += 3*g
      else:
        g = fr.gcd(i,j)
        tttt[i][j] = g
        tttt[j][i] = g
        ans += 3*g
for i in range(1, k-1):
  for j in range(i+1, k):
    for l in range(j+1, k+1):
      temp = tttt[i][j]
      temp2 = tttt[temp][l]
      ans+= 6*temp2
print(ans)
class Tree:
    value=0
    def __init__(self,position):
        self.position = position
        self.kid = set()
        self.value = 0

    def add_kid(self,it):
        self.kid.add(it)

    def add_val(self,val):
        self.value += val

    def calc(self,val=0):
        self.add_val(val)
        # print("called",self.position)
        for i in self.kid:
            if(i.position in visited)):
                continue
            visited.add(i.position)
            i.calc(self.value)

    def print_val(self):
        print(self.value,end=" ")

N,Q = [int(x) for x in input().split()]
ki = [Tree(i) for i in range(N)]

for i in range(N-1):
    a,b = [int(x) for x in input().split()]
    ki[a-1].add_kid(ki[b-1])
    ki[b-1].add_kid(ki[a-1])

for i in range(Q):
    position,val = [int(x) for x in input().split()]
    ki[position-1].add_val(val)

visited = set()
visited.add(0)
ki[0].calc()

for i in ki:
    i.print_val()
print()


### FIXED CODE ###

N,Q = [int(x) for x in input().split()]
ki = [0]*N
tr = [[] for _ in range(N)]

for i in range(N-1):
    a,b = [int(x)-1 for x in input().split()]
    tr[a].append(b)
    tr[b].append(a)

for i in range(Q):
    position,val = [int(x) for x in input().split()]
    ki[position-1] += val

stack =[0]
visited = set()
visited.add(0)

while stack:
    i = stack.pop()
    for j in tr[i]:
        if j in visited:
            continue
        visited.add(j)
        ki[j] += ki[i]
        stack.append(j)

for i in ki:
    print(i,end=" ")
print()
import numpy
while True:
    try:
        x1,y1,x2,y2,x3,y3,xp,yp=map(float,raw_input().split())
        AB=numpy.array([x2-x1,y2-y1])
        AP=numpy.array([xp-x1,yp-y1])
        BC=numpy.array([x3-x2,y3-y2])
        BP=numpy.array([xp-x2,yp-y2])
        CA=numpy.array([x1-x3,y1-y3])
        CP=numpy.array([xp-x3,yp-y3])
        #print numpy.cross(AB,AP)
        if (numpy.cross(AB,AP) < 0 and numpy.cross(BC,BP) < 0 and numpy.cross(CA,CP) < 0) or\
        (numpy.cross(AB,AP) > 0 and numpy.cross(BC,BP) > 0 and numpy.cross(CA,CP) > 0):
            print "YES"
        else:
            print "NO"
    except:
        break


### FIXED CODE ###

def f(a,b,c,d):
    return a*d-b*c

while True:
    try:
        x1,y1,x2,y2,x3,y3,xp,yp=map(float,raw_input().split())
        AB=[x2-x1,y2-y1]
        AP=[xp-x1,yp-y1]
        BC=[x3-x2,y3-y2]
        BP=[xp-x2,yp-y2]
        CA=[x1-x3,y1-y3]
        CP=[xp-x3,yp-y3]
        #print AB
        #print BC
        #print CA
        #print AP
        #print BP
        #print CP
        #print f(AB[0],AB[1],AP[0],AP[1])
        #print f(BC[0],BC[1],BP[0],BP[1])
        #print f(CA[0],CA[1],CP[0],CP[1])
        if (f(AB[0],AB[1],AP[0],AP[1]) < 0 and f(BC[0],BC[1],BP[0],BP[1]) < 0 and f(CA[0],CA[1],CP[0],CP[1]) < 0) or\
        (f(AB[0],AB[1],AP[0],AP[1]) > 0 and f(BC[0],BC[1],BP[0],BP[1]) > 0 and f(CA[0],CA[1],CP[0],CP[1]) > 0):
            print "YES"
        else:
            print "NO"
    except:
        break
n=int(input())
A=list(map(int,input().split()))
c=0
for i,a in enumerate(A):
  i+=1
  if i*a==1:
    c+=1
    A[0]=A[1]
    A[1]=1
  elif i==a:
    c+=1
    A[i]=A[i-1]
    A[i-1]=i
print(c)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))+[0]
c=0
for i in range(n):
  j=i+1
  a=A[i]
  if a==j:
    c+=1
    A[i]=A[i+1]
    A[i+1]=j
print(c)
T,Y,x,y=map(int,input().split())
a='0'
if T/2=x & Y/2=y:
  a='1'
print(T*Y/2,a)


### FIXED CODE ###

T,Y,x,y=map(int,input().split())
a='0'
if T/2==x and Y/2==y:
  a='1'
print(T*Y/2,a)
n = 0

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

n += int(N/(A+B)) * A

amari = N % (A+B)
n += min(amari, A)

print(n)

### FIXED CODE ###

s = input()
if "A" in s and "B" in s:
    print("Yes")
else:
    print("No")
A,B,C,K=input().split(" ")
if(A>=K):
  print(A)
else:
  if(K<=A+B):
    print(A)
  else:
    print(A-(K-A-B))

### FIXED CODE ###

A,B,C,K=map(int,input().split())
if(A>=K):
  print(K)
elif(A<K and A+B>=K):
  print(A)
else:
  print(A-(K-(A+B)))
def main():
	import sys
	sys.setrecursionlimit=10**6
	mod=998244353
	n,s=map(int,input().split())
	a=list(map(int,input().split()))
	from functools import lru_cache
	@lru_cache(maxsize=None)
	def dfs(x,y):
		if x==0:
			if y==0:
				return 1
			else:
				return 0
		r=dfs(x-1,y)*2%mod
		if y>0:
			if y-a[x-1]>=0:
				r+=dfs(x-1,y-a[x-1])
		r%=mod
		return r
	print(dfs(n,s))
main()

### FIXED CODE ###

mod=998244353
n,s=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*(s+1) for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
	for j in range(s+1):
		dp[i+1][j]+=2*dp[i][j]
		dp[i+1][j]%=mod
		if j+a[i]<=s:
			dp[i+1][j+a[i]]+=dp[i][j]
			dp[i+1][j+a[i]]%=mod
print(dp[n][s])
import numpy as np
lst = list(input().split())

num = len(lst)

A = lst[0] + lst[1]
B = lst[1] + lst[2]
C = lst[0] + lst[2]

print(min(np.array(A,B,C)))

### FIXED CODE ###

p,q,r = map(int,input().split())    
lst = [p,q,r]

A = lst[0] + lst[1]
B = lst[1] + lst[2]
C = lst[0] + lst[2]

print(min([A,B,C]))
S = input()
if S = 'AAA' and S = 'BBB':
  print('No')
else:
  print('Yes')

### FIXED CODE ###

S = input()
if S == 'AAA' or S == 'BBB':
  print('No')
else:
  print('Yes')
a,b,c=map(int,input()split())
if a<=c<=b:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a,b,c=map(int,input().split())
if a<=c<=b:
    print("Yes")
else:
    print("No")
code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False


cimport numpy as np
cdef extern from "<atcoder/fenwicktree>" namespace "atcoder" nogil:
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)

ctypedef np.int DTYPE_t

cdef class FenwickTree:
    cdef fenwick_tree[long long] *_thisptr
    def __cinit__(self, np.ndarray[DTYPE_t, ndim=1] array):
        cdef int N = array.size()
        self._thisptr = new fenwick_tree[long long](N)
        for i in range(N):
            self.add(i, array[i])
    cpdef void add(self, int p, long long x):
        self._thisptr.add(p, x)
    cpdef long long sum(self, int l, int r):
        return self._thisptr.sum(l, r)
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import FenwickTree
import numpy as np

N,Q = list(map(int,input().split()))
bit = FenwickTree(np.array(list(map(int,input().split())), dtype=np.int))

for i in range(Q):
    a,b,c = list(map(int,input().split()))
    if a==0:
        bit.add(b,c)
    else:
        print(bit.sum(b,c))

### FIXED CODE ###

class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)
        self.N0 = 1
        while self.N0*2 <= self.N:
            self.N0 *= 2

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret

    #you can use this function when the BIT has only non-negative values.
    def lower_bound(self, w):
        if w<=0:
            return 0
        x = 0
        k = self.N0
        while k>0:
            if x+k<=self.N:
                if self.bit[x+k-1]<w:
                    w-=self.bit[x+k-1]
                    x+=k
            k//=2
        return x


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

for i in range(Q):
    f,a,b = list(map(int,input().split()))
    if f==0:
        bit.add(a, b)
    else:
        if a==0:
            print(bit.sum(b-1))
        else:
            print(bit.sum(b-1)-bit.sum(a-1))
line = input()
num_a, num_b = [int(n) for n in line.split()][0]
is_it_possible = "Yay!"
if num_a > 8 or num_b > 8:
    is_it_possible = ":("
print(is_it_possible)

### FIXED CODE ###

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

if (a <= 8 and b <= 8):
	print("Yay!")
else:
	print(":(")
import heapq  
def priority(klr):
    return abs(klr[1]-klr[2])
              
def process(KLR):
    ans = 0   
    q = []    
    for klr in KLR:
        pr = priority(klr)
        if klr[0] < len(q) and q[0][0] < pr:
            tmp = heapq.heappop(q)
            ans += min(tmp[1], tmp[2])
        if klr[0] >= len(q):
            heapq.heappush(q, (pr, klr))
    for pr, klr in q:
        ans += max(klr[1], klr[2])
    return ans
              
              
def solve():  
    N = int(input())
    KLR = []  
    for _ in range(N):
        klr = list(map(int, input().split()))
        klr[0] -= 1 # convert to 0-based index to avoid confusion                                                                                                                                           
        KLR.append(klr)
    ans = 0   
    KLR_L = []
    KLR_R = []
    for klr in KLR:
        if klr[1] > klr[2]:
            KLR_L.append(klr)
        elif klr[1] < klr[2]:
            klr[0] = N-1-klr[0]-1
            if klr[0] < 0:
                ans += min(klr[1], klr[2])
            else:
                KLR_R.append(klr)
        else: 
            ans += klr[1]
    KLR_L.sort(key=lambda klr: klr[0])
    KLR_R.sort(key=lambda klr: klr[0])
    ans += process(KLR_L)
    ans += process(KLR_R)
    print(ans)
              
T = int(input())
              
for _ in range(T):
    solve()   
             

### FIXED CODE ###

import heapq  
def priority(klr):
    return abs(klr[1]-klr[2])
              
def process(KP):
    q = []    
    for kp in KP:
        if kp[0] < len(q) and len(q) > 0 and q[0] < kp[1]:
            heapq.heappop(q)
        if kp[0] >= len(q):
            heapq.heappush(q, kp[1])
    return sum(q)
              
def solve():  
    N = int(input())
    KLR = []  
    for _ in range(N):
        klr = list(map(int, input().split()))
        klr[0] -= 1 # convert to 0-based index to avoid confusion                                                                                                                                           
        KLR.append(klr)
    ans = 0   
    L = []    
    R = []    
    for klr in KLR:
        if klr[1] > klr[2]:
            ans += klr[2]
            L.append((klr[0], klr[1]-klr[2]))
        elif klr[1] < klr[2]:
            ans += klr[1]
            R.append((N-1-klr[0]-1, klr[2]-klr[1]))
        else: 
            ans += klr[1]
    L.sort(key=lambda kp: kp[0])
    R.sort(key=lambda kp: kp[0])
    ans += process(L)
    ans += process(R)
    print(ans)
              
T = int(input())
              
for _ in range(T):
    solve()
x=input()

a=int(x%500)

b=int((x-a*500)%5)

c=1000*a+5*b

print(c)

### FIXED CODE ###

x=int(input())

a=x//500

b=(x-a*500)//5

print(1000*a+5*b)
import sys
input = sys.stdin.readline
from collections import defaultdict

S = input().strip()
l = len(S)
dp = [[0 for _ in range(2019)] for i in range(l)]
for i in range(l):
    s = int(S[i])
    for j in range(2019):
        k = (10 * j + s) % 2019
        dp[i][k] = dp[i-1][j]
    dp[i][s] += 1

ans = 0
for i in range(l):
    ans += dp[i][0]
print(ans)


### FIXED CODE ###

S, W = list(map(int, input().split()))

if W >= S:
    print("unsafe")
else:
    print("safe")